佩尔方程最小解模板

1 import java.math.BigInteger;
2 import java.util.Scanner;
3
4 public class Main
5 {
6 public static void solve(int n)
7 {
8 BigInteger N, p1, p2, q1, q2, a0, a1, a2, g1, g2, h1, h2,p,q;
9 g1 = q2 = p1 = BigInteger.ZERO;
10 h1 = q1 = p2 = BigInteger.ONE;
11 a0 = a1 = BigInteger.valueOf((int)Math.sqrt(1.0*n));
12 BigInteger ans=a0.multiply(a0);
13 if(ans.equals(BigInteger.valueOf(n)))
14 {
15 System.out.println("No solution!");
16 return;
17 }
18 N = BigInteger.valueOf(n);
19 while (true)
20 {
21 g2 = a1.multiply(h1).subtract(g1);
22 h2 = N.subtract(g2.pow(2)).divide(h1);
23 a2 = g2.add(a0).divide(h2);
24 p = a1.multiply(p2).add(p1);
25 q = a1.multiply(q2).add(q1);
26 if (p.pow(2).subtract(N.multiply(q.pow(2))).compareTo(BigInteger.ONE) == 0) break;
27 g1 = g2;h1 = h2;a1 = a2;
28 p1 = p2;p2 = p;
29 q1 = q2;q2 = q;
30 }
31 System.out.println(p+" "+q);
32 }
33
34 public static void main(String[] args)
35 {
36 Scanner cin = new Scanner(System.in);
37 int t=cin.nextInt();
38 while(t>0)
39 {
40 int n=cin.nextInt();
41 if(n==0)
42 {
43 System.out.println("1 1");
44 continue;
45 }
46 solve(n);
47 t--;
48 }
49 }
50 }

1 #include
2 #define ll long long
3 #define dbg(x) cout<<#x<<" == "< 4 int rd(){int x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘){f=-1;} ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}return x*f;}
5 ll rdll(){ll x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘){f=-1;} ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}return x*f;}
6 using namespace std;
7 const int maxn=1e5+5;
8 const int mod=128;
9 const int Mod=13331;
10 ll a[20000];
11 bool pell_minimum_solution(ll n,ll &x0,ll &y0){
12 ll m=(ll)sqrt((double)n);
13 double sq=sqrt(n);
14 int i=0;
15 if(m*m==n)return false;//当n是完全平方数则佩尔方程无解
16 a[i++]=m;
17 ll b=m,c=1;
18 double tmp;
19 do{
20 c=(n-b*b)/c;
21 tmp=(sq+b)/c;
22 a[i++]=(ll)(floor(tmp));
23 b=a[i-1]*c-b;
24 //printf("%lld %lld %lld\n",a[i-1],b,c);
25 }while(a[i-1]!=2*a[0]);
26 ll p=1,q=0;
27 for(int j=i-2;j>=0;j--){
28 ll t=p;
29 p=q+p*a[j];
30 q=t;
31 //printf("a[%d]=%lld %lld %lld\n",j,a[j],p,q);
32 }
33 if((i-1)%2==0){x0=p;y0=q;}
34 else{x0=2*p*p+1;y0=2*p*q;}
35 return true;
36 }
37
38 int main(){
39 ll n,x,y;
40 int t=rd();
41 while(t--){
42 n=rdll();
43 if(pell_minimum_solution(n,x,y)){
44 printf("%d %d\n",x,y);
45 // printf("%lld^2-%lld*%lld^2=1\t",x,n,y);
46 // printf("%lld-%lld=1\n",x*x,n*y*y);
47 }
48 }
49 }