zoj3759（待解决+算法木有问题+but需要java大数）














  1 //zoj3759
  2 //http://www.bingfengsa.com/info/18001.html
  3 //学习笔记(仅仅是填充学习博文中的知识点而以)
  4 /*
  5 【题目要求】：
  6 找到：x(x+1)/2=ky^2      -x^2-x+2ky^2=0          (2x+1)^2-8k*y^2=1
  7       x^2=ky^2           x^2-ky^2=0;              特殊
  8       x(3x-1)/2=ky^2     3x^2-x-2ky^2=0         （6x-1)^2-24ky^2=1
  9       x(2x-1)=ky^2       2x^2-x-2ky^2=0          (4x-1)^2-8y^2=1
 10       x=ky^2             0x^2-x+ky^2=0;          特殊
 11 右边是统一化成的z^2-ny^2=0的形式,z代换了x
 12 
 13 【换元】：z^2-ny^2=1
 14 【佩尔方程】：
 15 显然这个方程有正整数解，则x，y才可能有整数解，
 16 ///////佩尔方程的知识/////////
 17 一、下面的不定方程称为佩尔（Pell）方程：
 18 x^2 - ny^2= 1  设n是正整数
 19 如果d是完全平方数，那么只有平凡解(-1,0),(1,0)
 20 如果不是，一定有无穷多组正整数解
 21 二、递归解：
 22 x[i+1]=x[1]*x[i]+n*y[1]*y[i]
 23 y[i+1]=x[1]*y[i]+y[1]*x[i]
 24 三、基本解(x1,y1)：
 25 首先根据根号n的渐进连分数（h/k)表示，找出前几项，察看x=h,y=k带入后是否是一组解。
 26 是，则得到了(x1,y1)
 27 四、渐进连分数的生成（如截图）：
 28 五、佩尔方程的解是指数增长的（很少）
 29 六、佩尔方程最小解的生成
 30 from : http://blog.csdn.net/accelerator_916852/article/details/20411727
 31 bool pell( int D, int& x, int& y ) {//D就是上文的N
 32     int sqrtD = sqrt(D + 0.0);//这里应该处理精度才行
 33     if( sqrtD * sqrtD == D ) return false;
 34     int c = sqrtD, q = D - c * c, a = (c + sqrtD) / q;
 35     int step = 0;
 36     int X[] = { 1, sqrtD };
 37     int Y[] = { 0, 1 };
 38     while( true ) {
 39         X[step] = a * X[step^1] + X[step];
 40         Y[step] = a * Y[step^1] + Y[step];
 41         c = a * q - c;
 42         q = (D - c * c) / q;
 43         a = (c + sqrtD) / q;
 44         step ^= 1;
 45         if( c == sqrtD && q == 1 && step ) {
 46             x = X[0], y = Y[0];
 47             return true;
 48         }
 49     }
 50 }
 51 ///////佩尔方程的知识/////////
 52 【继续】 现在我们找到了z1，y1，能得到所有的z[i],y[i],现在我们通过这些解，找到最小的x、y正整数解就可以了
 53 【特殊方程的解决】：(题目没要求计算)
 54  1、x^2-ky^2=0;k判断k是否是完全平方数即可
 55  2、0x^2-x+ky^2=0;直接解出x即可
 56  */
 57 
 58 #include<iostream>
 59 #include<string.h>
 60 #include<stdio.h>
 61 #include<stdlib.h>
 62 #include<cmath>
 63 #include<algorithm>
 64 #include<queue>
 65 #include<stack>
 66 #include<set>
 67 #include<map>
 68 #define LL unsigned long long
 69 #define maxn 510
 70 #define INF 99999
 71 using namespace std;
 72 
 73 int k,kind;
 74 
 75 bool pell( int D, LL& x, LL& y ) {//D就是上文的N
 76     LL sqrtD = (LL)sqrt(D + 0.0);//这里应该处理精度才行
 77     if( sqrtD * sqrtD == D || (sqrtD+1) * (sqrtD+1)==D ) return false;
 78     LL c = sqrtD, q = D - c * c, a = (c + sqrtD) / q;
 79     LL step = 0;
 80     LL X[] = { 1, sqrtD };
 81     LL Y[] = { 0, 1 };
 82     while( true ) {
 83         X[step] = a * X[step^1] + X[step];
 84         Y[step] = a * Y[step^1] + Y[step];
 85         c = a * q - c;
 86         q = (D - c * c) / q;
 87         a = (c + sqrtD) / q;
 88         step ^= 1;
 89         if( c == sqrtD && q == 1 && step ) {
 90             x = X[0], y = Y[0];
 91             return true;
 92         }
 93     }
 94 }
 95 
 96 void solve(int N,int a,int b)//写成x=(z+a)/b的形式
 97 {
 98     LL z1,y1;
 99 //    int zi,yi;
100     LL ansx,ansy;
101     bool ok=pell(N,z1,y1);
102     if (!ok)
103     {
104         printf("Impossible!
");
105         return ;
106     }
107     if ((z1+a)%b==0) {ansx=(z1+a)/b,ansy=y1;cout<<ansx<<" "<<ansy<<endl;}
108     else printf("Impossible!
");
109 }
110 int main()
111 {
112     while(cin>>kind)
113     {
114         if (kind==0) break;
115         cin>>k;
116         if (kind==3) solve(8*k,-1,2);
117         else if (kind==5) solve(24*k,1,6);
118         else if (kind==6) solve(8*k,1,4);
119     }
120     return 0;
121 }