扩展GCD-时间复杂性
题目：
计算循环语句的执行频次 for (i = A; i != B; i += C) x += 1;
其中A, B, C, i都是k位无符号整数。
输入：
A B C k, 其中0<k<32
输出：
输出执行频次数，如果是无穷，则输出“forever”
#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;
}
应该是益出了：
#include <iostream>
#include <cmath>
using namespace std;
#define LL long long int main()
{
int k;
cin >> k;
LL a = 1;
LL b = a << k;
LL c = 1 << k;
cout << "b: " << b << endl;
cout << "c: " << c << endl; return 0;
} /*
30
b: 1073741824
c: 1073741824 31
b: 2147483648
c: -2147483648 32
b: 4294967296
c: 1 33
b: 8589934592
c: 2 34
b: 17179869184
c: 4
*/