poj 2115 C Looooops(扩展欧几里德算法)
?題意：
? ? ? ?對于for(i=A ; i!=B ;i+=C)循環語句，問在k位存儲系統中循環幾次才會結束。
比如：當k=4時，存儲的數 i 在0-15之間循環。(本題默認為無符號)
否則輸出死循環。
二，思路：
本題利用擴展歐幾里德算法求線性同余方程，設循環次數為 x ,則解方程 (A + C*x) % 2^k = B;求出最小正整數 x。?
1，化簡方程化為求線性同余方程標準式 ax ≡ b (mod n);
2，擴展歐幾里德算法求解線性同余方程 C*x ≡ B-A (mod 2^k);上面的紅色公式轉化為這個式子沒有看懂（兩者之間的轉化）
3，求出最小非負整數解。
1、化簡：(A + C*x) mod 2^K = B ?--> ?C*x mod 2^k = B-A ?--> ? C*x ≡ B-A (mod 2^k);??
(A+x*C)%(2^k)=B?變形(2^k)*y+B=A+C*x ==> ?C*x+(-(2^k)*y)=B-A;這個變形比較實用吧
2、求線性同余方程 C*x ≡ B-A (mod 2^k) ,
就相當于求二元一次方程 C*x + 2^k * y = B-A?
i,代入擴展歐幾里德算法，求解方程 C*x + 2^k * y = gcd(C , 2^k) ;?ii,利用方程 C*x + 2^k * y = gcd(C , 2^k)的解 x0 和x1 = x0 * c/d 求出原方程 a*x + b*y = c 的解 x1 ;前提是：d|c (c 能被 d 整除);
3、利用周期性變化求最小的非負整數解 公式: x1 = (x1 % (b/d) + (b/d) ) % (b/d);? ? ? 若方程的C*x + 2^k * y = B-A 的一組整數解為(x1 , y1)，則它的任意整數解為(x1 + k * (b/d) , y1 - k * (a/d) ) ( k取任意整數 ), T = b/d就為 x1 增長的周期?
i，若x1為負值，取最大的非正值：x1 = x1 % T ; 若x1為正值，以下兩步無影響;?
ii，取正 ：x1 = x1 + T ;
iii， 防止 i 中的 x1=0 即 ii 中的 x1=T ：x1 = x1 % T ;
看到數論概論中的得到的一些總結（和上面的（2）ii類似：
已知ax+by=1的一組解為（x1,y1)，那么其他組的解為（x1+k*b,y1-k*a)(k為任意整數)?當ax+by=gcd(a,b)=d時，其他組的解變為（x1+k*b/d,y1-k*a/d),因此b/d就成為了一個增長周期
#include <iostream> using namespace std; void exgcd(long long a,long long b,long long &d,long long &x,long long &y) {if(!b)//b==0說明上層a%b==0上層的b（這層的a)為最大公因數,則a*x+b*y=a{d=a; //遞歸到這時候a就是最大公因數（ d用來存儲gcd(a,b)的值）//結合上一層exgcd(b,a%b,d,y,x)x=1;y=0;}else{exgcd(b,a%b,d,y,x);y=y-x*(a/b);//...........} } int main() {long long A,B,C,x,y,T,d;int k;while(cin>>A>>B>>C>>k&&(A+B+C+k)){long long n=1LL<<k;//n = 1 * 2^k ;exgcd(C,n,d,x,y);//a*x + b*y = c ,C*x + 2^k * y =B-Aif((B-A)%d!=0)//上面（2）中的性質ii{cout<<"FOREVER"<<endl;continue;}x=x*(B-A)/d;T=n/d;x=(x%T+T)%T;cout<<x<<endl;}return 0; }總結
以上是生活随笔為你收集整理的poj 2115 C Looooops(扩展欧几里德算法)的全部內容，希望文章能夠幫你解決所遇到的問題。
