首先是题意理解,我理解为int类型最大取到2^(k-1),超过这个值就会跳到-2^(k-1),这跟我们正常的运算是一样的只不过int类型的最大最小值变了。
我们可以将-2^(k-1)看作0点,2^(k-2)看作中点,2*2^(k-2)看作终点,到达终点后跳回起点,这样和《五指山》那一题如出一辙。
所以此题我认为可以照猫画虎《五指山》那一题
1299.五指山:https://www.acwing.com/problem/content/1301/
下面是代码(做过五指山一定可以看懂):
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL & x, LL & y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
LL a, b, c, k;
while(scanf("%lld%lld%lld%lld", &a, &b, &c, &k) && (a || b || c || k))
{
LL mid = 1LL << k - 1;
LL len = 2 * mid;
a = mid + a, b = mid + b;
LL x, y;
LL gcd = exgcd(len, c, x, y);
if((b - a) % gcd) printf("FOREVER\n");
else
{
y *= (b - a) / gcd;
len /= gcd;
printf("%lld\n", (y % len + len) % len);
}
}
return 0;
}