题意:给出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; }