410498: GYM104027 K 零时困境 II

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. 零时困境 IItime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

当法伊、西格玛、戴安娜第三次次醒来时,发现他们再一次被关在了一个全新的密室中,有了之前几次的经验,他们显得并不吃惊。果然,密室里的小电视里,又出现了零的身影,他沙哑的嗓音也又一次从电视的扬声器中传出:"别担心,这次只要玩一个数学游戏,猜中了,你们就可以安全的离开这里"。

"零这家伙,一定又在捣什么鬼,我才不信他会有这么好心。"西格玛喃喃自语道。

游戏的规则是:

使用如下的随机数生成器连续生成n个整数,请你帮忙计算所生成的所有数的最大公约数。

unsigned long long k1, k2, K;

void setSeed(unsigned long long a, unsigned long long b, unsigned long long c) {
k1 = a;
k2 = b;
K = c;
}

unsigned long long xorShift128Plus() {
unsigned long long k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return (k2 + k4) % K + 1;
}

现在,你知道了代码中的abc,你想知道生成的随机数的前n个数的最大公约数。

你可以使用以下代码获得答案:

unsigned long long solve(unsigned long long a, unsigned long long b, unsigned long long c, unsigned long long n) {
setSeed(a, b, c);
unsigned long long res = xorShift128Plus();
for (a = 1; a != n; ++a) {
res = __gcd(res, xorShift128Plus());
}
return res;
}
Input

一行,四个整数abcn,如题目描述所示。(0 ≤ a, b, c, n ≤ 264 - 1,n ≥ 100 * c

Output

一个整数,表示答案。

ExampleInput
1 1 1 100
Output
1

加入题单

上一题 下一题 算法标签: