大体推推 会出来这个式子 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}
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
#include<map>
using namespace std;
#define N 35000
#define LL long long
int p[N],g;
map<int,int>f;
void init()
{
int i,j;
for(i = ; i <= ; i++)
if(!f[i])
{
for(j = i+i ; j < N ; j+=i)
f[j] = ;
}
for(i = ; i < N ; i++)
if(!f[i])
p[++g] = i;
}
void exgcd(int a,int b,int &x,int &y)
{
if(b==)
{
x=;y=;
return ;
}
exgcd(b,a%b,x,y);
int t = x;
x = y;
y = t-a/b*y;
}
int main()
{
int k,n,x,y,a,b,i;
init();
cin>>k;
while(k--)
{
cin>>n;
int tx = sqrt(n*1.0);
for(i = ; i <= g ; i++)
{
int o = p[i];
if(n%o==)
{
a = o;
b = n/o;
break;
}
if(o>tx) break;
}
exgcd(a,b,x,y);
int x1 = x<? a*x+a*b:a*x;
exgcd(b,a,x,y);
int x2 = x<? b*x+b*a:b*x;
printf("0 1 %d %d\n",min(x1,x2),max(x1,x2));
}
return ;
}