首页 > ACM题库 > HDU-杭电 > HDU 3292-No more tricks, Mr Nanguo-快速幂-[解题报告]HOJ
2014
03-13

HDU 3292-No more tricks, Mr Nanguo-快速幂-[解题报告]HOJ

No more tricks, Mr Nanguo

问题描述 :

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.

输入:

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).

输出:

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).

样例输入:

2 999888
3 1000001
4 8373

样例输出:

7181
600 
No answers can meet such conditions

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

题目大意:求出第K打的满足方程X^2-N*Y^2=1的解。

解题思路:很明显的pell方程,需要用快速幂求解答案。

pell方程求解:http://blog.csdn.net/ruptins/article/details/21301165

通过代码:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
#define MOD 8191

bool pell( int D, int& x, int& y ) {
    int sqrtD = sqrt(D + 0.0);
    if( sqrtD * sqrtD == D ) return false;
    int c = sqrtD, q = D - c * c, a = (c + sqrtD) / q;
    int step = 0;
    int X[] = { 1, sqrtD };
    int Y[] = { 0, 1 };
    while( true ) {
        X[step] = a * X[step^1] + X[step];
        Y[step] = a * Y[step^1] + Y[step];
        c = a * q - c;
        q = (D - c * c) / q;
        a = (c + sqrtD) / q;
        step ^= 1;
        if( c == sqrtD && q == 1 && step ) {
            x = X[0], y = Y[0];
            return true;
        }
    }
}
int a[40][2][2];
int b[2][2];
int c[2][2];
int solve(int E){
    for (int i=1;i<=35;i++)
        for (int j=0;j<=1;j++)
            for (int k=0;k<=1;k++)
                for (int t=0;t<=1;t++)
                    a[i][j][k]=(a[i][j][k]+a[i-1][j][t]*a[i-1][t][k])%MOD;
    int l=0;
    b[0][0]=b[1][1]=1;
    b[0][1]=b[1][0]=0;
    while (E>0){
        if (E%2){
            memset(c,0,sizeof(c));
            for (int i=0;i<=1;i++)
                for (int j=0;j<=1;j++)
                    for (int t=0;t<=1;t++)
                        c[i][j]=(c[i][j]+b[i][t]*a[l][t][j])%MOD;
            memcpy(b,c,sizeof(c));
        }
        l++;
        E/=2;
    }
    return (b[0][0]*a[0][0][0]+b[0][1]*a[0][1][0])%MOD;
}

int main(){
    int N,K;
    while (scanf("%d%d",&N,&K)==2){
        int x,y;
        if (!pell(N,x,y)){
            printf("No answers can meet such conditions\n");
            continue;
        }
        memset(a,0,sizeof(a));
        a[0][0][0]=x%MOD;
        a[0][0][1]=N*y%MOD;
        a[0][1][0]=y%MOD;
        a[0][1][1]=x%MOD;
        printf("%d\n",solve(K-1));

    }
    return 0;
}

参考:http://blog.csdn.net/ruptins/article/details/21302185


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”