題目鏈接：點擊查看

題目大意：執行一個循環：

for (variable = A; variable != B; variable += C)

? ? ?statement;

問在2的k次冪的范圍內最少需要執行多少次

題目分析：我們可以先利用同余方程列出公式：

進而可以化成這陣形式：

這樣直接用拓展歐幾里得求出X就是答案了

代碼：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;LL ex_gcd(LL a,LL b,LL &x,LL &y) {if(b==0){x=1;y=0;return a;}LL ans=ex_gcd(b,a%b,y,x);y-=a/b*x;return ans; }int main() { // freopen("input.txt","r",stdin);LL a,b,c,k;while(scanf("%lld%lld%lld%lld",&a,&b,&c,&k)!=EOF&&a+b+c+k){LL x,y;LL d=ex_gcd(c,1LL<<k,x,y);if((b-a)%d!=0)printf("FOREVER\n");else{LL ans=x*(b-a)/d;LL mod=(1LL<<k)/d;ans=(ans%mod+mod)%mod;printf("%lld\n",ans);}}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2115 C Looooops(扩展欧几里得)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。