No more tricks, Mr Nanguo
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
题目类型：Pell方程
算法分析：首先判断N是否是完全平方数，若是则无解。否则使用暴力枚举的方法求出特解，然后构造矩阵快速幂求解第k个解即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define i64 long long const int INF = 0x7FFFFFFF; const int MOD = 8191; const double EPS = 1e-6; const double PI = 2 * acos (0.0); const int maxn = 2; long long n = 2;//表示方阵的尺寸，必须恰好为运算的大小 //申请变量 struct Mat { long long mat[maxn][maxn]; }; //重载Mat乘法运算 Mat operator * (Mat a, Mat b) { Mat c; memset (c.mat, 0, sizeof (c.mat)); for (long long k = 0; k < n; k++) { for (long long i = 0; i < n; i++) { if (a.mat[i][k] == 0) continue; for (long long j = 0; j < n; j++) { if (b.mat[k][j] == 0) continue; c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD; } } } return c; } //重载Mat乘幂运算 Mat operator ^ (Mat a, long long k) { Mat c; for (long long i = 0; i < n; i++) for(long long j = 0; j < n; j++) c.mat[i][j] = (i == j); while (k) { if(k & 1) c = c * a; a = a * a; k >>= 1; } return c; } long long val, k; void Get (long long &x, long long &y) { for (long long ty = 1; ; ty++) { long long tx = (long long) sqrt (1 + val * ty * ty + 0.0); if (tx * tx - val * ty * ty == 1) { x = tx, y = ty; return ; } } } int main() { // CPPFF; while (cin >> val >> k) { long long tt = (long long ) sqrt (val + 0.0); if (tt * tt == val) cout << "No answers can meet such conditions" << endl; else { long long x1, y1; Get (x1, y1); // cout << x1 << " " << y1 << endl; Mat aa; aa.mat[0][0] = x1, aa.mat[0][1] = val * y1; aa.mat[1][0] = y1, aa.mat[1][1] = x1; Mat bb; bb.mat[0][0] = x1, bb.mat[1][0] = y1; Mat res; res = aa ^ (k - 1); res = res * bb; cout << res.mat[0][0] << endl; } } return 0; } |
- « 上一篇：hdu3065
- hdu3501：下一篇 »