UVALive 4270 Discrete Square Roots 模方程,数论

2019-04-14 19:54发布

站内文章 / 模拟电子
16632 0 1751
// author:latstars // time:2016-09-03 00:33:19 // 题目: UVALive 4270 Discrete Square Roots模方程 // 分类:数论,模方程 // 题意:求所有满足条件r^2=x(mod m)的r // 题目已经给定了一个初始的r,x,m // 不妨设新的r1^2=x(mod m) // 那么就有r^2-r1^2=0(mod m) // 所以就有(r+r1)(r-r1)=0(mod m) // (r+r1)(r-r1)=k*m // 不妨枚举a*b=n // 使得满足(r+r1)%a=0 (r-r1)%b=0 // 那么就满足所要求的条件 // r+r1=a*k1 r-r1=a*k2 // r1=a*k1-r=r-a*k2 // 所以a*k1+b*k2=2*r // 就是解模方程组了 // 之后把k1带入求出r1就是结果了 // UVA - 1426 Discrete Square Roots (模方程) // error:忘记判断模方程无解的情况 // 用while循环暴力使模数为负超时 #include #include #include #include #include #include using namespace std; const int maxn=100; typedef long long LL; LL mx,n,r; void exgcd(LL a,LL b,LL & d,LL & x,LL & y) { if(b==0){ x=1;y=0;d=a; return; } else{ exgcd(b,a%b,d,y,x); y-=a/b*x; } } void cal(LL a,set& ans) { LL b=n/a; LL d,x,y; exgcd(a,b,d,x,y); if((2*r)%d!=0) return; x=x*2*r/d; x=(x%(b/d)+(b/d))%(b/d); LL r1=a*x-r; // while(r1>0) // r1-=a*(b/d); while(r1if(r1>=0&&(r1*r1)%n==mx) ans.insert(r1); r1+=a*(b/d); } } void solve(void) { set ans; LL sz=sqrt(n+0.5); for(LL a=1;a<=sz;a++){ if(n%a!=0) continue; cal(a,ans); cal(n/a,ans); } for(set::iterator it=ans.begin();it!=ans.end();it++){ printf(" %lld",(*it)); } puts(""); } int main() { int t=1; while(scanf("%lld %lld %lld",&mx,&n,&r)!=EOF&&(mx|n|r)){ printf("Case %d:",t++); solve(); } return 0; }

热门文章