【数学一本通 第一章】C Looooops [POJ 2115]

题目：

题目链接：C Looooops
题解：原题可以转化为：$cx\equiv b?a(mod{2}^k)$，解个方程即可。

代码：

#include<stdio.h>
#define LL long long 
using namespace std;
LL A,B,C,kk;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    LL s,t;if(!b){
    x=1,y=0;return a;}s=exgcd(b,a%b,x,y);t=x,x=y,y=t-a/b*y;return s;
}
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);}
int main()
{
    while(1){
    scanf("%lld%lld%lld%lld",&A,&B,&C,&kk);if(!A&&!B&&!C&&!kk) return 0;LL a=C,c=B-A,b=(LL)1<<kk,x,y;LL t=gcd(a,b);if(c%t!=0){
    printf("FOREVER\n");continue;}a/=t; b/=t; c/=t;exgcd(a,b,x,y);x=((c*x)%b+b)%b;printf("%lld\n",x); }return 0;
} 

continue……（打算开下一章了，，，）