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;
}


目录
相关文章
【AcWing】曼哈顿距离
【AcWing】曼哈顿距离
65 0
HDU7018.Banzhuan(计算几何+贪心)
HDU7018.Banzhuan(计算几何+贪心)
104 0
HDU7018.Banzhuan(计算几何+贪心)
AcWing 658. 一元二次方程公式
AcWing 658. 一元二次方程公式
87 0
AcWing 658. 一元二次方程公式
|
Java 机器学习/深度学习
UESTC 30 &&HDU 2544最短路【Floyd求解裸题】
最短路 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 65817    Accepted Submission(s): 28794 Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。
1147 0
|
并行计算 算法 Java
HDU 1874 畅通工程续【Floyd算法实现】
畅通工程续 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 53806    Accepted Submission(s): 20092 Problem Description 某省自从实行了很多年的畅通工程计划后,终于修建了很多路。
1086 0
|
人工智能
Uva 11300 Spreading the Wealth(递推,中位数)
Spreading the Wealth Problem A Communist regime is trying to redistribute wealth in a village. They have have decided to sit everyone around a circular table.
913 0
数论 + 公式 - HDU 4335 What is N?
What is N?  Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=4335   Mean:  给你三个数b、P、M,让你求有多少个n满足下式。
860 0
|
容器
hdu3388 Coprime【容斥原理】
Problem Description Please write a program to calculate the k-th positive integer that is coprime with m and n simultaneously.
1132 0
|
机器学习/深度学习 BI