原题链接：https://www.acwing.com/problem/content/1303/

算法整理部分

欧几里得算法（辗转相除法）

给定a b两个正整数 求a b的最大公约数

ll gcd(ll a,ll b){
	return b == 0 ? a : gcd(b, a % b);
}

扩展欧几里得算法

给予两个整数a b，必存在整数x、y使得ax + by = gcd(a,b)
在求得一组x y的同时求得gcd(a,b)
x y其中一个有可能是负数
如果a或者b是负数 那么将求出来的x/y取反即可
很多情况下等式右边并不是gcd(a,b) 因此要乘以相应的倍数 但是这个数一定是gcd(a,b)的倍数
同时求出来的 x y是这个等式的一组解 假设为x0 y0
得到方程组
x=x0+k*(b/gcd(a,b))
y=y0-k*(a/gcd(a,b))
要求x的最小值 我们发现 一定是在x0的基础上改变了一定倍数的b/gcd(a,b)倍 所以x的最小值就是x0%(b/gcd(a,b))

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

题目

对于 C 语言的循环语句，形如：

for (variable = A; variable != B; variable += C)
  statement;

请问在 k 位存储系统中循环几次才会结束。

若在有限次内结束，则输出循环次数。否则输出死循环。

思路

注意这个题 是k位存储系统中 所以是存在一个循环加一圈之后相等 比如在16位系统中 一开始a=3 c=1 b每次加2 最后是能够达成条件的
a%(1<<x)可以实现k位操作系统这一条件
所以我们可以得到
(a+x*c)%2^k=b
等价于
a+x*c-y*2^k=b
等价于
x*c-y*2^k=b-a
只有 x y 两个未知量 因此使用扩展欧几里得算法
求出gcd(a,b)
这时候如果求出的这个最大公约数不是b-a的倍数 那么就是无解
之后两边同时乘(b-a)/gcd(a,b)
回顾一下贝祖等式
ax+by=gcd(a,b)
这里的b 就是1<<k
因此可以用上文的结论得到
xmin=x(这个x是乘了倍数之后的x)%(b/gcd(a,b))

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<int, int> PII;
const int maxn = 110;
const int INF = 0x3f3f3f3f;

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		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;
	int k;
	while (cin >> a >> b >> c >> k, a || b || c || k)
	{
		ll x, y;
		ll z = 1ll << k;
		ll d = exgcd(c, z, x, y); //注意传进去的参数
		if ((b - a) % d)
		{
			cout << "FOREVER" << endl;
			continue;
		}
		x *= (b - a) / d;
		z /= d;
		cout << (x%z + z) % z << endl;
	}
	return 0;
}