poj2115（扩展欧基里德定理）

题目链接：https://vjudge.net/problem/POJ-2115

题意：模拟for循环for(int i=A;i!=B;i+=C)，且数据范围为k位无符号数以内，即0~1<<k-1，如果能循环为有限次则输出循环次数，否则输出FOREVER。

思路：典型的扩展欧基里德题。题意即求Cx=B-A (mod 1<<k)，可化为Cx+(1<<k)y=B-A (mod 1<<k)。不访令a=C,b=1<<k,c=B-A,即求ax+by=c (mod b)的解x。根据扩展欧基里德定理，该方程有解的条件为gcd(a,b)|c。令d=gcd(a,b)，则ax0+by0=d可通过扩展欧基里德计算得到x0，y0和d的值。则原问题的解x=(c/d*x0%(b/d)+b/d)%(b/d)。理由是，c/d*x0可能超出1<<k（b）的范围，注意到ax+by=d等价与a(x+m*b/d)+b(y-m*a/d)=d，m为任意值，即通过对b/d取模能得到最小非负整数解，因为可能为负值，所以取模后仍要加上b/d，并再次取模。

AC代码：

 #include<cstdio>

 using namespace std;

 typedef long long LL;

 LL A,B,C,a,b,c,k;

 void ex_gcd(LL a,LL b,LL &x,LL &y,LL &d){

     if(!b) x=,y=,d=a;

     else{ex_gcd(b,a%b,y,x,d);y-=x*(a/b);}

 }

 int main(){

     while(~scanf("%lld%lld%lld%lld",&A,&B,&C,&k),k){

         a=C,b=1LL<<k;c=(B-A)%b;

         LL x,y,d;

         ex_gcd(a,b,x,y,d);

         if(c%d==)

             printf("%lld\n",(c/d*x%(b/d)+b/d)%(b/d));

         else printf("FOREVER\n");

     }

     return ;

 }

巴特西

poj2115（扩展欧基里德定理）

最新文章

热门文章