POJ2115 - C Looooops(扩展欧几里得)

题目大意

求同余方程Cx≡B-A(2^k)的最小正整数解

题解

可以转化为Cx-(2^k)y=B-A,然后用扩展欧几里得解出即可。。。

代码:

#include <iostream>
using namespace std;
typedef long long LL;
void extended_gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
if(!b)
{
d=a,x=1,y=0;
}
else
{
extended_gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int main()
{
LL a,b,k,c,x,y,d,p;
while(cin>>a>>b>>c>>k&&a+b+c+k)
{
p=1LL<<k;
extended_gcd(c,p,d,x,y);
if((b-a)%d)
{
cout<<"FOREVER"<<endl;
continue;
}
x=x*(b-a)/d;
x=(x%(p/d)+p/d)%(p/d);
cout<<x<<endl;
}
return 0;
}
上一篇:Roslyn还出现这么低级的错误,不应该呀!


下一篇:html与xhtml有什么区别?