poj2115C Looooops

http://poj.org/problem?id=2115

參考人家的如下

如i=65534，當i+=3時，i=1

其實就是 i=(65534+3)%(2^16)=1

有了這些思想，設對于某組數據要循環x次結束，那么本題就很容易得到方程：

x=[(B-A+2^k)%2^k] /C

即 Cx=(B-A)(mod 2^k)? 此方程為模線性方程，本題就是求X的值。

為了統一

令a=C??

? b=B-A?

? n=2^k

那么原模線性方程變形為：

ax=b (mod n)

該方程有解的充要條件為 gcd(a,n) | b ，即 b% gcd(a,n)==0

令d=gcd(a,n)

有該方程的最小整數解為 x = e (mod n/d)

其中e = [x0 mod(n/d) + n/d] mod (n/d) ，x0為方程的最小解

那么原題就是要計算b% gcd(a,n)是否為0，若為0則計算最小整數解，否則輸出FOREVER

據說。。

最小解 X=x*(B/d)%K;之后，為了保證X為最小正整數解需要做如下變換
(X+K)%(K/d)

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stdlib.h>
 5 #include<cmath>
 6 #define LL long long
 7 using namespace std;
 8 LL exgcd(LL a,LL b,LL &x,LL &y)
 9 {
10     if(b == 0)
11     {
12         x = 1; y = 0; return a;
13     }
14     LL d = exgcd(b, a % b,x,y);
15     LL temp = x;
16     x = y;
17     y = temp - a / b * y;
18     return d;
19 }
20 int main()
21 {
22     LL A,B,C,k;
23     while(cin>>A>>B>>C>>k)
24     {
25         if(!A&&!B&&!C&&!k)
26             break;
27         LL a = C;
28         LL b = B-A;
29         LL n = 1LL<<k;
30         LL x,y;
31         LL d = exgcd(a,n,x,y);
32         if(b%d!=0)
33         {
34             puts("FOREVER");
35             continue;
36         }
37         x = x*(b/d)%n;
38         x = (x+n)%(n/d);
39         cout<<x<<endl;
40     }
41     return 0;
42 }

轉載于:https://www.cnblogs.com/shangyu/archive/2013/02/19/2917724.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/378838.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/378838.shtml
英文地址，請注明出處：http://en.pswp.cn/news/378838.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！