大体推推 会出来这个式子 x(x-1) = k*n;n = p*q ;x(x-1)%(p*q)==0;
因为p,q都为素数 那也就是说x和x-1中必定包含这两个数 而且一个里面只能有一个 不然会大于等于N
当上面的k=0时 x=0||x=1 这是固定的
然后 {x-pi=0; (x-1)-qi = 1}化这一组 就会变成pi-qi=1 这就变成了扩展欧几里得 必定存在一组解 解出来带入一下 注意一下负数就可以了 下一组同样这样计算
{x-pi=1; (x-1)-qi = 0}
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<map> 8 using namespace std; 9 #define N 35000 10 #define LL long long 11 int p[N],g; 12 map<int,int>f; 13 void init() 14 { 15 int i,j; 16 for(i = 2; i <= 32000 ; i++) 17 if(!f[i]) 18 { 19 for(j = i+i ; j < N ; j+=i) 20 f[j] = 1; 21 } 22 for(i = 2; i < N ; i++) 23 if(!f[i]) 24 p[++g] = i; 25 } 26 void exgcd(int a,int b,int &x,int &y) 27 { 28 if(b==0) 29 { 30 x=1;y=0; 31 return ; 32 } 33 exgcd(b,a%b,x,y); 34 int t = x; 35 x = y; 36 y = t-a/b*y; 37 } 38 int main() 39 { 40 int k,n,x,y,a,b,i; 41 init(); 42 cin>>k; 43 while(k--) 44 { 45 cin>>n; 46 int tx = sqrt(n*1.0); 47 for(i = 1; i <= g ; i++) 48 { 49 int o = p[i]; 50 if(n%o==0) 51 { 52 a = o; 53 b = n/o; 54 break; 55 } 56 if(o>tx) break; 57 } 58 exgcd(a,b,x,y); 59 int x1 = x<0? a*x+a*b:a*x; 60 exgcd(b,a,x,y); 61 int x2 = x<0? b*x+b*a:b*x; 62 printf("0 1 %d %d ",min(x1,x2),max(x1,x2)); 63 } 64 return 0; 65 }