711
HDU 2281 pell方程
題意：給出N找出最大的n滿足n<=N；
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=2;
const long long oo=1e18;
typedef struct
{
long long m[MAX][MAX];
} Matrix;
Matrix I= {1,0,
0,1
};
Matrix P,data;
Matrix matrixmul(Matrix a,Matrix b) //矩陣乘法
{
int i,j,k;
Matrix c;
for (i = 0 ; i < MAX; i++)
for (j = 0; j < MAX; j++)
{
c.m[i][j] = 0;
for (k=0; k<MAX; k++)
c.m[i][j]+=a.m[i][k]*b.m[k][j];
c.m[i][j];
}
return c;
}
int main()
{
long long ans[50][2];
P.m[0][0]=P.m[1][1]=7;
P.m[0][1]=48,P.m[1][0]=1;
data=I;
ans[0][0]=ans[0][1]=1;
int num=1;
for(int i=1; i<50; i++)
{
data=matrixmul(data,P);
long long nowx=data.m[0][0]*7+data.m[0][1],nowy=data.m[1][0]*7+data.m[1][1];
if((nowx-3)%4==0)
ans[num][0]=(nowx-3)/4,ans[num][1]=nowy,num++;
if(ans[num-1][0]>oo)
break;
}
long long n;
while(~scanf("%I64d",&n),n)
for(int i=0; i<8; i++)
if(ans[i][0]>n||i==7)
{
printf("%I64d %I64d\n",i==7?ans[7][0]:ans[i-1][0],i==7?ans[7][1]:ans[i-1][1]);
break;
}
return 0;
}
最後更新：2017-04-03 16:48:46