POJ 2115 C Looooops（exgcd）

发布时间：2020-12-16 09:16:03 所属栏目：百科来源：网络整理

导读：嗯... ? 题目链接：http://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 #includecstdio 2 #includeiostream 3 4 usin

嗯...

题目链接：http://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,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,y);
17         if(c % g) printf("FOREVERn");
18         else{
19             c /= g; b /= g;
20             printf("%lldn",(x % b * c % b + b) % b);
21         }
22     }
23     return 0;
24 }

AC代码

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!