75-扩展GCD-时间复杂度

扩展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;
}