Uva 138-Street Numbers（佩尔方程） - c++编程基础

题目链接：点击打开链接

题意：一条街上有n个房子编号从1到n 设某人的房子编号为k 求满足 1+2+3+..(k-1)=(k+1)+...+n 的10组n，k值

两边求和化简得 n^2+n-2k^2=0; 两边同乘4 -> 4n^2+4n+1-8k^2=1; -> (2n+1)^2-2(2k)^2=1;

令 x=2n+1 y=2k 得 x^2-2y^2=1; 形如 x^2-ny^2=1 (n为任意正整数) 的方程称为佩尔方程，很容易求出其最小解 (x0,y0)

然后 xi=x0*x(i-1)+n*y0*y(i-1)

yi=y0*x(i-1)+x0*y(i-1) ;递推可得方程所有解

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 10000002 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 10000007 #define pp pair
               
                 #define ull unsigned long long using namespace std; int main() { int x[11]={3},y[11]={2}; for(int i=1;i<=10;i++){ x[i]=x[i-1]*x[0]+2*y[i-1]*y[0]; y[i]=x[i-1]*y[0]+y[i-1]*x[0]; int n=(x[i]-1)/2,k=y[i]/2; printf("%10d%10d\n",k,n); } return 0; }