HDU 3292 佩爾方程入門+矩陣快速幂--你想解二進制二次方程嗎？

題意：求x^2-n*y^2=1 按x排序第k大的解。

一.原理

佩爾方程：X^2-d Y^2=1,d不為完全平方數的整數，有無窮多個解

為什麼d不能為完全平方數：

(x+

y)(x-

y)=1

x隻能取正負1，y取0，就不會有無窮多組解

遞推式如下：

于是構造矩陣：

二.具體實作：

①search():

 x1,y1可以暴力解得，因為以x排序,x與y正相關，是以找最小的x，y從1開始枚舉，找到第一個x即為最小

②注意判斷N是否是完全平方數

③矩陣快速幂細節：

設個結構體，友善定義多個二維數組，比如機關矩陣，答案矩陣

矩陣相乘裡面就要%，不單單隻是快速幂那裡%

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=(ll)8191 ;
const ll MAXN=(ll)4;
typedef struct
{
	ll m[MAXN][MAXN];  //後面要建構一堆矩陣 
}Ma;
Ma pre,a;
ll x,y,N;

void search()//找出第一個解x,y，暴力 
{
	y=1;
	while(1)
	{
		x=(long long)sqrt(N*y*y+1);
		if(x*x-N*y*y==1)break;
		y++;
		
	}
 } 

void init()//用xy初始化第一個矩陣 
{
	a.m[0][0]=x%M;
	a.m[0][1]=N*y%M;
	a.m[1][0]=y%M;
	a.m[1][1]=x%M;
	pre.m[0][0]=pre.m[1][1]=1;
	pre.m[0][1]=pre.m[1][0]=0;
}

Ma multi(Ma p,Ma q)
{
	Ma c;
	for(int i=0;i<2;i++)
	  for(int j=0;j<2;j++)
	  {
	     c.m[i][j]=0;//一定要初始化 
	    for(int k=0;k<2;k++)
	    {
	    	c.m[i][j]+=p.m[i][k]*q.m[k][j];
		}
		c.m[i][j]%=M;//一定要% 
	}
		
		
		return c;
}

Ma power(ll k)
{
	Ma c=a;
	Ma ans=pre;
	while(k)
	{
		if(k&1)  //先特殊處理奇數 
		{
			ans=multi(ans,c);
			k--;
		}
		k/=2;
		c=multi(c,c);
	}
	
	return ans;
}

int main()
{
  ll K;
  while(cin>>N>>K)
  {
  	if((ll)sqrt(N)*(ll)sqrt(N)==N)//是完全平方
	  {
	  	printf("No answers can meet such conditions\n");
         continue;
	   } 
	   search();
	   init();
	   a=power(K-1);
	   x=(a.m[0][0]*x%M+a.m[0][1]*y%M) %M;    //再乘剩下那個矩陣
	   y=(a.m[1][0]*x%M+a.m[1][1]*y%M)%M;
	   printf("%lld\n",x); 
  }
  return 0;
}