B - C Looooops POJ - 2115 (扩展欧几里得)
题目链接:https://cn.vjudge.net/contest/276376#problem/B
题目大意:for( int i= A ; i != B; i+ = c ),然后给你A,B,C,K,前三个是for循环里面的变量,K指的是每一次ABC三个数都对2^k进行取余,然后问你要使得这个循环停止,最少的循环次数,如果是一个死循环,就输出"FOREVER".
具体思路:和我之前写的那一篇博客思路差不多,证明过程直接上图。
一开始没有注意到B,等号右边应该是B-A,而不是B,以后注意下(不过结果正负的情况下,只有在后b调就可以了)。
AC代码:
1 #include<iostream> 2 #include<stack> 3 #include<cmath> 4 #include<queue> 5 #include<stdio.h> 6 #include<algorithm> 7 using namespace std; 8 # define ll long long 9 const int maxn = 1e5+100; 10 ll quickpow(ll ti) 11 { 12 ll ans=2; 13 ti--; 14 ll tmp=2; 15 while(ti) 16 { 17 if(ti&1) 18 ans=ans*tmp; 19 tmp*=tmp; 20 ti>>=1; 21 } 22 return ans; 23 } 24 ll xo,yo; 25 ll exgcd(ll a,ll b) 26 { 27 if(b==0) 28 { 29 xo=1; 30 yo=0; 31 return a; 32 } 33 ll gcd=exgcd(b,a%b); 34 ll tmp=yo; 35 yo=xo-a/b*yo; 36 xo=tmp; 37 return gcd; 38 } 39 int main() 40 { 41 ll a,b,c,k; 42 while(~scanf("%lld %lld %lld %lld",&a,&b,&c,&k)&&(a+b+c+k)) 43 { 44 ll tmp=quickpow(k); 45 ll t=exgcd(c,tmp); 46 if((b-a)%t) 47 printf("FOREVER\n"); 48 else 49 { 50 ll tmp1=tmp/t; 51 printf("%lld\n",((b-a)*xo/t%tmp1+tmp1)%tmp1); 52 } 53 } 54 return 0; 55 }