862
技術社區[雲棲]
URAL 1204 中國剩餘定理
題意：給出一個n n為兩個素數的乘積，讓求滿足方程 x*x=x ( mod n ) 且x<n的解。
給上麵等式變形有x*(x-1)=0 ( mod p*q ) 則有 x = 0 ( mod p) x = 1 ( mod q ) 或者 x = 1( mod p) x = 0 ( mod q )，由於p,q,互素，所以可以用中國剩餘定理求出最小的正整數解。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define maxn 100000
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
if(b==0)
{
x=1,y=0,d=a;
return;
}
exgcd(b,a%b,d,x,y);
long long temp=x;
x=y,y=temp-(a/b)*y;
}
long long m[5],a[5],n;
int china(int r)
{
long long i,mi,x0,y0,d,ans=0;
for(int i=0; i<r; i++)
{
mi=n/m[i];
exgcd(mi,m[i],d,x0,y0);
ans=(ans+mi*x0*a[i])%n;
}
if(ans<0) ans+=n;
return ans;
}
bool isprime[maxn];
int prime[maxn],nprime;
void getprime()
{
memset(isprime,1,sizeof(isprime));
long long i,j;
nprime=0;
for(i=2; i<maxn; i++)
if(isprime[i])
{
prime[nprime++]=i;
for(j=i*i; j<maxn; j+=i) isprime[j]=0;
}
}
int main()
{
getprime();
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
a[0]=0,a[1]=1;
int l=(int)sqrt(n*1.0);
for(int i=0; prime[i]<=l; i++)
if(n%prime[i]==0) m[0]=prime[i],m[1]=n/prime[i];
int ans1=china(2),ans2;
swap(m[0],m[1]);
ans2=china(2);
if(ans1>ans2) swap(ans1,ans2);
printf("0 1 %d %d\n",ans1,ans2);
}
return 0;
}
最後更新：2017-04-03 15:22:13