POJ 2115 线性模方程

2019-04-14 16:08发布

站内文章 / 模拟电子
11158 0 1736
#include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long ll A,B,C,k,a,b; ll ext_gcd(ll a,ll n,ll &x,ll &y) { if(n==0) { x=1;y=0; return a; } ll d=ext_gcd(n,a%n,x,y); ll x1=x,y1=y; x=y1; y=x1-y1*(a/n); return d; } int main () { while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)!=EOF) { if(A==0 && B==0 && C==0 && k==0) break; ll n=1,x,y; for(int i=1;i<=k;++i) n=n*2; b=B-A; while(b<0) b+=n; a=C; ll d=ext_gcd(a,n,x,y); if(b%d) printf("FOREVER "); else { ll e=x*(b/d); if(e<0) { if(e%(n/d)==0) e=0; else e+=(-e/(n/d)+1)*(n/d); } else { if(e%(n/d)==0) e=0; else e-=e/(n/d)*(n/d); } printf("%lld ",e); } } return 0; }

热门文章