题解 | #C Looooops#
C Looooops
https://ac.nowcoder.com/acm/contest/980/J
C Looooops
思路
k 位存储系统，意思是能储存的最大数为 2^k-1，越过了会变为 0
所以 A + x*C B（mod 2^k）
利用扩欧求得 x 即可
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll get_mod(ll a,ll b){
return (a%b+b)%b;
}
int main(){
ll A,B,C,k;
while(cin>>A>>B>>C>>k){
if(A==0&&B==0&&C==0&&k==0) break;
ll a=C,b=(ll)1<<k,c=B-A;
ll x=0,y=0;
ll d=exgcd(a,b,x,y);
if(c%d) puts("FOREVER");
else{
x*=c/d;
x=get_mod(x,b/d);
cout<<x<<endl;
}
}
return 0;
}
查看30道真题和解析
