扩展gcd-时间复杂性
题目内容：
计算循环语句的执行频次 for(i=A; i!=B ; i+=C) x+=1;
其中A,B,C,i都是k位无符号整数。
输入描述
A B C k, 其中0<k<32
输出描述
输出执行频次数，如果是无穷，则输出“forever”
输入样例
3 7 2 16
输出样例2
看到题还是很蒙蔽，虽然提示了知识点：
gcd(a,b)为求a,b的最大公约数；
ex_gcd(a,b,x,y)则是求 ax + by = gcd(a,b)的一组解
由ax + by = gcd(a,b) 和 ax1 + by1 = c 就可以求后一个方程的解了：x1 = x * (n / gcd(a,b)), y1 = y * (n / gcd(a,b));
但注意：先计算Gcd(a,b)，若c不能被Gcd(a,b)整除，则方程无整数解
此时 x1,y1只是方程 ax + by = c的一组解，他们的通解为
x = x0 + tn;
y = y0 - tm;
(x0, y0为最正小整数解)
则有 a(x0 + tn) + b(y0 - tm) = c,同时又有ax0 + by0 = c，化简上式子：
a*t*n - b*t*m = 0;
则 an = bm 要想n,m最小就是使得an，bm都为a，b的最小公倍数：
an = (a*b)/gcd(a,b) -> n = b/gcd(a,b);
同理：m = a /gcd(a,b);
则：x0 = (x % n + n)%n；
y0 = (y % m + m)%m;
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
//#define LL long long
typedef long long LL;
LL gcd(LL a, LL b)
{
return b == 0 ? a : gcd(b, a%b);
} LL ex_gcd(LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
LL ans = ex_gcd(b, a%b, x, y);
LL temp = x;
x = y;
y = temp - a / b*y;
return ans;
} int main(){
LL A, B, C, k;
cin >> A >> B >> C >> k;
LL a = C, n = B - A, x, y; //b = pow(2,k),
//b改成b = 1 << k就会出错
LL d = 1;
LL b = d << k;
cout << "b: " << b << endl;
int gc = gcd(a,b);
if(A == 0 && B == 0){
cout << 0 << endl;
return 0;
}
if(C == 0 || gc == 0 || n % gc != 0){
cout << "forever" << endl;
return 0;
}
ex_gcd(a,b,x,y); //返回ax + by = gcd(a,b)的解
x = x * (n / gc); //得到通解x即：ax + by = n
LL nn = b / gc; //通解x的最小周期
x = (x % nn + nn) % nn; //得到最小解
cout << x << endl;
return 0;
}