HDU 3292 pell方程

简介:

题意:求x^2+n*y^2=1 按x排序第k大的解。

题目就是求佩尔方程,用矩阵连乘的方法,当n为完全平方数的时候无解。

如果我们求出Pell方程的最小正整数解后,就可以根据递推式求出所有的解。




则根据上式我们可以构造矩阵,然后就可以快速幂了。




这样就可以求出第k大的解。


HDU3292题就要用到上面的矩阵方法求第k大的解。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define M 8191
const int MAX=2;
typedef struct
{
    long long m[MAX][MAX];
} Matrix;
Matrix I= {1,0,
           0,1
          };
Matrix P;
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]%(M))*(b.m[k][j]%(M)))%(M);
            c.m[i][j] %=M;
        }
    return c;
}
Matrix quickpow(long long n)
{
    Matrix m = P, b = I;
    while (n >= 1)
    {
        if (n & 1)
            b = matrixmul(b,m);
        n = n >> 1;
        m = matrixmul(m,m);
    }
    return b;
}
int main()
{
    long long n,k,x,y;
    while(~scanf("%I64d%I64d",&n,&k))
    {
        if(n==4||n==9||n==16||n==25)
        {
            puts("No answers can meet such conditions");
            continue;
        }
        for(y=1;; y++)
        {
            x=(long long)sqrt(double(y*y*n+1));
            if(x*x==y*y*n+1)
                break;
        }
        P.m[0][0]=P.m[1][1]=x%M;
        P.m[0][1]=(n*y)%M,P.m[1][0]=y%M;
        Matrix ans=quickpow(k-1);
        printf("%I64d\n",((ans.m[0][0]*x)%M+(ans.m[0][1]*y)%M)%M);
    }
    return 0;
}



目录
相关文章
|
Java C++
poj 1503 高精度加法
把输入的数加起来,输入0表示结束。 先看我Java代码,用BigINteger类很多东西都不需要考虑,比如前导0什么的,很方便。不过java效率低点,平均用时600ms,C/C++可以0ms过。
43 1
|
5月前
|
机器学习/深度学习 算法 C++
【洛谷 P2240】【深基12.例1】部分背包问题 题解(贪心算法)
**深基12.例1**是部分背包问题,$N$堆金币,每堆$(m_i, v_i)$,$T$承重限制。按金币单价降序装包,保证价值最大化。输入$N,T$及每堆金币详情,输出两位小数的最大价值。示例:输入$4,50$,输出$240.00$。AC代码使用C++,通过排序和迭代实现。
67 0
|
6月前
|
机器学习/深度学习
N皇后问题(HDU—2253)
N皇后问题(HDU—2253)
poj 1185 炮兵阵地 (状态压缩dp)
如果你是刚刚开始做状态压缩dp,我建议你先看看 poj 3254 Corn Fields 这是一道比这一题更简单,更容易入门的题目。 还有在代码中我用了一个很巧妙的方法求一个数二进制数中1的个数 具体请看我博客中 x& (x - 1)==0 这篇文章 链接 。
41 1
hdu1406 完数 (水题)
hdu1406 完数 (水题)
47 0
AcWing 822. 走方格
AcWing 822. 走方格
79 0
AcWing 822. 走方格
|
网络架构
POJ-1005,I Think I Need a Houseboat(数学题)
POJ-1005,I Think I Need a Houseboat(数学题)
HDU-1058,Humble Numbers(丑数打表)
HDU-1058,Humble Numbers(丑数打表)
HDU-1262,寻找素数对(素数打表)
HDU-1262,寻找素数对(素数打表)
HDOJ/HDU 2537 8球胜负(水题.简单的判断)
HDOJ/HDU 2537 8球胜负(水题.简单的判断)
104 0