POJ 2115 C Looooops（exgcd）如何改写为长尾词？
- 内容介绍
- 文章标签
- 相关推荐
本文共计287个文字，预计阅读时间需要2分钟。
题目链接：http://poj.org/problem?id=2115
(A + s + C)^(k)=B + (A + s + C)^kB (mod 2^k) + s * C - m * 2^k=B - A + ax + by=c
有一个问题，b不一定必须是负的，反正a和b的线性组合集合都一样，所以此题不需要y * AC代码：
1
嗯...
题目链接：poj.org/problem?id=2115
(A+s*C)%2^k=B (A+s*C)≡B(mod 2^k) s*C-m*2^k=B-A ax+by=c 有一个问题，b没必要是负的，反正正负a和b的线性组合集都一样，况且此题不需要y AC代码：1 #include<cstdio> 2 #include<iostream> 3 4 using namespace std; 5 6 inline void exgcd(long long a, long long b, long long &g, long long &x, long long &y){ 7 if(!b) { g = a; x = 1; y = 0;} 8 else { exgcd(b, a % b, g, y, x); y -= x * (a / b);} 9 } 10 11 int main(){ 12 long long a, b, c, A, B, C, k, g, x, y; 13 while(~scanf("%lld%lld%lld%lld", &A, &B, &C, &k)){ 14 if(!A && !B && !C && !k) break; 15 a = C; b = 1ll << k; c = B - A; 16 exgcd(a, b, g, x, y); 17 if(c % g) printf("FOREVER\n"); 18 else{ 19 c /= g; b /= g; 20 printf("%lld\n", (x % b * c % b + b) % b); 21 } 22 } 23 return 0; 24 } AC代码
本文共计287个文字，预计阅读时间需要2分钟。
题目链接：http://poj.org/problem?id=2115
(A + s + C)^(k)=B + (A + s + C)^kB (mod 2^k) + s * C - m * 2^k=B - A + ax + by=c
有一个问题，b不一定必须是负的，反正a和b的线性组合集合都一样，所以此题不需要y * AC代码：
1
嗯...
题目链接：poj.org/problem?id=2115
(A+s*C)%2^k=B (A+s*C)≡B(mod 2^k) s*C-m*2^k=B-A ax+by=c 有一个问题，b没必要是负的，反正正负a和b的线性组合集都一样，况且此题不需要y AC代码：1 #include<cstdio> 2 #include<iostream> 3 4 using namespace std; 5 6 inline void exgcd(long long a, long long b, long long &g, long long &x, long long &y){ 7 if(!b) { g = a; x = 1; y = 0;} 8 else { exgcd(b, a % b, g, y, x); y -= x * (a / b);} 9 } 10 11 int main(){ 12 long long a, b, c, A, B, C, k, g, x, y; 13 while(~scanf("%lld%lld%lld%lld", &A, &B, &C, &k)){ 14 if(!A && !B && !C && !k) break; 15 a = C; b = 1ll << k; c = B - A; 16 exgcd(a, b, g, x, y); 17 if(c % g) printf("FOREVER\n"); 18 else{ 19 c /= g; b /= g; 20 printf("%lld\n", (x % b * c % b + b) % b); 21 } 22 } 23 return 0; 24 } AC代码