【扩展欧几里得】poj2115 C Looooops
题意大概是让你求(A+Cx) mod 2^k = B的最小非负整数解。
若(B-A) mod gcd(C,2^k) = 0，就有解，否则无解。
式子可以化成Cx + 2^k*y = B - A，可以用扩展欧几里得得到一组解。
设M=gcd(C,2^k),X=x*(B-A)/M
要想得到最小非负整数解的话，就是(X%(L/M)+L/M)%(L/M)。
证明略。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
ll A,B,C,k,GCD,X,Y;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
d=a;
x=1;
y=0;
}
else
{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int main()
{
while(1){
scanf("%d%d%d%d",&A,&B,&C,&k);
if(A==0 && B==0 && C==0 && k==0)
break;
GCD=__gcd(C,1ll<<k);
if((B-A)%GCD!=0)
puts("FOREVER");
else
{
exgcd(C,1ll<<k,GCD,X,Y);
X=X*(B-A)/GCD;
cout<<((X%((1ll<<k)/GCD)+((1ll<<k)/GCD))%((1ll<<k)/GCD))<<endl;
}
}
return 0;
}
优质内容筛选与推荐>>1、【NS2】NS2修改MAC协议（转载）
2、javap -s 查看java方法签名
3、没有循环的JavaScript
4、灵魂
5、P3649 [APIO2014]回文串