【poj 2115】C Looooops（数论--拓展欧几里德求解同余方程模版题）

题意：有一个在k位无符号整数下的模型：for (variable = A; variable != B; variable += C) statement; 问循环的次数，若“永不停息”(←_←)*，就输出"FOREVER"。

解法：用拓展欧几里德方法求出gcd最大公因数，再利用同余性质转化，求同余方程，或者不定方程。其中题目可化为 a+cx=b(mod 2^k) → cx=b-a(mod 2^k)，求最小正整数解。也是求解同余方程。

先将方程化为一般形式：ax=c(mod p) → ax+py=c 。若 gcd(a,p)|c，就可以利用 ax+py=gcd(a,b)(mod p) [一般没有mod p] ，再把变量 x,y 乘上 c/gcd(a,b) 就是答案了。而要求最小正整数解，就是根据 ax+py=gcd(a,p) → a(x+p/gcd(a,p))+p(y-a/gcd(a,p)=gcd(a,p) ，所有的 x' 都满足 x+p/gcd(a,p) 来进行调整，并且取模。因为每对 x 与 x' 都相差 p/gcd(a,p)，那么根据同余的定义，x 和 x' 关于模 p/gcd(a,p) 同余，所以可以一直取模来调整。而对于 p/gcd(a,p) ，为正时取模才有保证最非负的意义。

注意——位运算超过30位时，尽管变量为long long，也要在之前加上强制转型(long long)。见代码的24行......之前我一次比赛，数组初始化是long long类型的，也要在数字后面加上"LL"或" l l "。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6 typedef long long LL;

 7

 8 LL mabs(LL x) {return x>0?x:-x;}

 9 LL exgcd(LL a,LL b,LL& x,LL& y)

10 {

11     if (!b) {x=1,y=0; return a;}

12     LL d,tx,ty;

13     d=exgcd(b,a%b,tx,ty);//bx'+(a%b)y'=1(mod p)

14     x=ty,y=tx-(a/b)*ty;//ay'+b(x'-t*y')=1(mod p)

15     return d;

16 }

17 int main()

18 {

19     LL aa,bb,cc,pp;

20     while (1)

21     {

22       scanf("%I64d%I64d%I64d%I64d",&aa,&bb,&cc,&pp);

23       if (!aa && !bb && !cc && !pp) break;

24       LL a=cc,b=(LL)1<<pp,c=bb-aa,p=(LL)1<<pp;

25       LL d,x,y;//cx=b-a(mod 2^k)-->cx+2^k*y=b-a-->gcd(c,2^k)=1才有解

26       d=exgcd(a,b,x,y);

27       if (c%d!=0) printf("FOREVER\n");

28       else

29       {

30         x=(x*(c/d))%p;//ax+by=c(mod p)的解

31         LL t=mabs(b/d);

32         x=(x%t+t)%t;//最小非负整数解

33         if (!x) x+=t;//为0时要调整
34         printf("%I64d\n",x);

35       }

36     }

37     return 0;

38 }

巴特西

【poj 2115】C Looooops（数论--拓展欧几里德求解同余方程模版题）

最新文章

热门文章

巴特西

【poj 2115】C Looooops（数论--拓展欧几里德 求解同余方程 模版题）

最新文章

热门文章

【poj 2115】C Looooops（数论--拓展欧几里德求解同余方程模版题）