http://acm.timus.ru/problem.aspx?space=1&num=1204數(shù)論，歐幾里德擴(kuò)展。x*x-x=pq*a*b，其中a*b=n，為質(zhì)數(shù)。可化解得x*(x-1)=ap*qb。則可知x=ap,(x-1)=qb或者x=qb,(x-1)=ap。則ap-qb=1或者qb-ap=1;因?yàn)間cd(a,b)=1,則extended_euclid可以求得p，q。解之：
#include<stdio.h>
int x,y,p[400000],prime[40000];
int ex_euclid(int a,int b)
{
int c,tmp;
if (b==0)
{
x=1;y=0;
return a;
}
c=ex_euclid(b,a%b);
tmp=x;x=y;y=tmp-a/b*y;
return c;
}
int main()
{
int i,j,a,b,n,now,t;
memset(p,0,sizeof(p));
now=2;t=0;
while (now<400000)
{
t++;prime[t]=now;
i=now;
while (i<400000)
{
p[i]=1;
i+=now;
}
while (p[now])
now++;
}
scanf("%d",&n);
while (scanf("%d",&n)==1)
{
i=1;
while (i<t&&n%prime[i])
i++;
a=prime[i];
b=n/a;
ex_euclid(a,b);
if ((a*x+n)%n<(y*b+n)%n)
printf("%d %d %d %d\n",0,1,(a*x+n)%n,(y*b+n)%n);
else
printf("%d %d %d %d\n",0,1,(y*b+n)%n,(a*x+n)%n);
}
}
數(shù)學(xué)公式，慢慢研究化解，總有辦法的。嘿嘿，
為什么timus上提交的時(shí)候我的兩個(gè)大數(shù)組沒(méi)有放在前面而發(fā)生了
Crash (stack overflow)呢？怎么回事啊？？？