poj2115 Looooops 扩展欧几里德的应用
好开心又做出一道，看样子做数论一定要先看书，认认真真仔仔细细的看一下各种重要的性质 及其用途，然后第一次接触的题目 边想边看别人的怎么做的，这样做出第一道题目后，后面的题目就完全可以自己思考啦
设要+t次，列出方程 c*t-p*2^k=b-a（p是一个正整数，这里的内存相当于一个长度为2^k的圆圈，满了就重来一圈）
这样子就符合扩展欧几里德的方程基本式了
然后令 c*t-p*2^k=gcd(c,2^k);
gcd=exgcd(c,t0,2^l,p0);
解出t0;那么t=t0*(b-a)/gcd；
那么答案救出来了
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8//const ll INF=9999999999999;#define M 400000100#define inf 0xfffffffusing namespace std;//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;//vector<int>G[30012];LL extgcd(LL a,LL &x,LL b,LL &y){if(b==0){x=1;y=0;return a;}LL r=extgcd(b,x,a%b,y);LL t=x;x=y;y=t-a/b*y;return r;}int main(void){LL a,b,c,k;while(cin>>a>>b>>c>>k){if(a+b+c+k == 0)break;LL MOD=(LL)1<<k;//这里要强制转化，坑了我好多遍，倒霉LL t0,p0;LL gcd=extgcd(c,t0,MOD,p0);LL m=b-a;if(m%gcd!=0){puts("FOREVER");continue;}LL t=(t0*m/gcd+MOD)%MOD;//这里一定要注意，最好每一道题目都加上MOD在模MOD，因为有可能t0值是负的t=(t%(MOD/gcd)+(MOD/gcd))%(MOD/gcd);//这里要模的值要看清楚 是MODgcd，而不是MOD；cout<<t<<endl;}}