poj2115 Looooops 扩展欧几里德
x=[ (B-A+2^k)%2^k ]/C
C*X=(B-A+2^k)%2^k
一开始 方程不知道咋办 后来 看到别人统一一下变量 顿时 愚蠢的我感觉清晰了一点点
令a=C, b=B-A, MOD=2^k;
方程变成了 ax=(n+MOD)%MOD;
看到某个大神贴的一张图片很给力 我也贴一下，顺便贴一下他的解析过程，很容易懂得，一开始学数论 不可能自己完全推出来 都是要看要做，做多了应该就行了把，我天赋比较差的，求保佑：！
该方程有解的充要条件为 gcd(a,n) | b ，即 b% gcd(a,n)==0
令d=gcd(a,n)
有该方程的 最小整数解为 x = e (mod n/d)
其中e = [x0 mod(n/d) + n/d] mod (n/d) ，x0为方程的最小解
那么原题就是要计算b% gcd(a,n)是否为0，若为0则计算最小整数解，否则输出FOREVER
当有解时，关键在于计算最大公约数 d=gcd(a,n) 与 最小解x0
参考《算法导论》，引入欧几里得扩展方程 d=ax+by ，
通过EXTENDED_EUCLID算法（P571）求得d、x、y值，其中返回的x就是最小解x0，求d的原理是辗转相除法（欧几里德算法）
再利用MODULAR-LINEAR-EQUATION-SOLVER算法（P564）通过x0计算x值。注意x0可能为负，因此要先 + n/d 再模n/d。
#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-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//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 b,LL &x,LL &y){if(b==0){x=1;y=0;return a;}LL d=extgcd(b,a%b,x,y);LL temp=x;x=y;y=temp-a/b*y;return d;}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 b=B-A;LL a=C;LL x,y;LL d=extgcd(a,MOD,x,y);if(b%d!=0)cout<<"FOREVER"<<endl;else{x=(x*(b/d)+MOD)%MOD;x=(x%(MOD/d)+MOD/d)%(MOD/d);cout<<x<<endl;}}}