<原># HDU 3292 No more tricks, Mr Nanguo [佩尔方程+矩阵]【数论】

HDU 3292 No more tricks, Mr Nanguo [佩尔方程+矩阵]【数论】

2016年09月26日 19:21:33 Tabris_ 阅读数:345

个人分类: hdu
===== 各OJ =====

===== 数论 =====


博客爬取于2019-04-18 17:19:22
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52673118

题目链接: http://acm.split.hdu.edu.cn/showproblem.php?pid=3292

———————————————————–.
No more tricks, Mr Nanguo

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K
(Java/Others)
Total Submission(s): 378 Accepted Submission(s): 250

Problem Description
Now Sailormoon girls want to tell you a ancient idiom story named “be there
just to make up the number”. The story can be described by the following
words.
In the period of the Warring States (475-221 BC), there was a state called Qi.
The king of Qi was so fond of the yu, a wind instrument, that he had a band of
many musicians play for him every afternoon. The number of musicians is just a
square number.Beacuse a square formation is very good-looking.Each row and
each column have X musicians.
The king was most satisfied with the band and the harmonies they performed.
Little did the king know that a member of the band, Nan Guo, was not even a
musician. In fact, Nan Guo knew nothing about the yu. But he somehow managed
to pass himself off as a yu player by sitting right at the back, pretending to
play the instrument. The king was none the wiser. But Nan Guo’s charade came
to an end when the king’s son succeeded him. The new king, unlike his father,
he decided to divide the musicians of band into some equal small parts. He
also wants the number of each part is square number. Of course, Nan Guo soon
realized his foolish would expose, and he found himself without a band to hide
in anymore.So he run away soon.
After he leave,the number of band is Satisfactory. Because the number of band
now would be divided into some equal parts,and the number of each part is also
a square number.Each row and each column all have Y musicians.

Input
There are multiple test cases. Each case contains a positive integer N ( 2 <=
N < 29). It means the band was divided into N equal parts. The folloing number
is also a positive integer K ( K < 10^9).

Output
There may have many positive integers X,Y can meet such conditions.But you
should calculate the Kth smaller answer of X. The Kth smaller answer means
there are K – 1 answers are smaller than them. Beacuse the answer may be very
large.So print the value of X % 8191.If there is no answers can meet such
conditions,print “No answers can meet such conditions”.

Sample Input
2 999888
3 1000001
4 8373

Sample Output
7181
600
No answers can meet such conditions

Author
B.A.C

Source
2010 “HDU-Sailormoon” Programming Contest

—————————————-.
题目大意
南郭先生的故事想必大家都知道
就是最开始有 X*X
后来南郭走了
变成了 N Y*Y
之后题目给你一个N 和K
让你求满足题意的第K大的X值是多少。。。

解题思路
题目显然能够得到下面的方程
XX=1+NYY
转化一下就是
X
X-NYY=1

这就是标准的佩尔方程了 不知道佩尔方程的话可以先去百度下.
首先N很小 所以可以先暴力的跑出特解 然后用迭代的方式求得第K大的解
X(n)=X(n-1)X(1)+N*Y(n-1)Y(1)
Y(n)=X(n-1)Y(1)+Y(n-1)X(1)

因为K很大 所以要用矩阵优化一下

矩阵略

附本题代码
———————————.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

#define INF 0x3f3f3f3f
#define pb push_back
#define abs(a) (a)>0?(a):-(a)
#define lalal puts("*******");

typedef long long int LL ;
/**********************************/
const int MOD = 8191;
const int M = 2;
struct Matrix
{
    LL m[M][M];
    void clearO()
    {
        for(int i=0; i<M; i++) //初始化零矩阵
            for(int j=0; j<M; j++)
                m[i][j]= 0;
    }
    void clearE()
    {
        for(int i=0; i<M; i++) //初始化单位矩阵
            for(int j=0; j<M; j++)
                m[i][j]= (i==j);
    }
    void display()
    {
        for(int i=0; i<M; i++)
        {
            for(int j=0; j<M; j++)
                printf("%d ",m[i][j]);
            puts("");
        }
    }
};

Matrix operator * (Matrix a,Matrix b)
{
    Matrix c;
    c.clearO();

    for(int k=0; k<M; k++)
        for(int i=0; i<M; i++) //实现矩阵乘法
        {
            if(a.m[i][k] == 0)  continue;
            for(int j=0; j<M; j++)
            {
                if(b.m[k][j] ==  0)    continue;
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            }
        }
    return c;
}

Matrix operator ^ (Matrix a,LL b)
{
    Matrix c;
    c.clearE();
    while(b)
    {
        if(b&1) c= c * a ;
        b >>= 1;
        a = a * a ;
    }
    return c;
}
int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        if(4==n||9==n||16==n||25==n)
        {
            puts("No answers can meet such conditions");
            continue;
        }

        LL x,y;

        int tmp,tem;
        for(int i=1;; i++)
        {
            tmp=n*i*i+1;
            tem=sqrt(tmp);
            if(tmp==tem*tem)
            {
                x=tem,y=i;
                break;
            }
        }

        Matrix a,b;
        a.clearO(),b.clearO();
        a.m[0][0] = x%MOD,a.m[0][1] = y%MOD;

        b.m[0][0] = x%MOD,b.m[0][1] = y%MOD;
        b.m[1][0] = n*y%MOD,b.m[1][1] = x%MOD;

        b=b^(k-1);
        a=a*b;

        printf("%I64d\n",a.m[0][0]);

        //printf("%I64d %I64d\n",x,y);

    }
    return 0;
}

 上一篇
<原>#  杂(模板) <原># 杂(模板)
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2016-09-27
下一篇 
<原>#  POJ 1305 Fermat vs. Pythagoras [本源毕达哥拉斯不等式]【数论】 <原># POJ 1305 Fermat vs. Pythagoras [本源毕达哥拉斯不等式]【数论】
这是你自定义的文章摘要内容,如果这个属性有值,文章卡片摘要就显示这段文字,否则程序会自动截取文章的部分内容作为摘要
2016-09-21
  目录