Quadratic Residues
Background
In 1801, Carl Friedrich Gauss (1777-1855) published his "Disquisitiones Arithmeticae", which basically created modern number theory and is still being sold today. One of the many topics treated in his book was the problem of quadratic residues. Consider a prime number p and an integer a !≡ 0 (mod p). Then a is called a quadratic residue mod p if there is an integer x such that
x2 ≡ a (mod p), and a quadratic non residue otherwise. Lagrange (1752-1833) introduced the following notation, called the "Legendre symbol":For the calculation of these symbol there are the following rules, valid only for distinct odd prime numbers p, q and integers a, b not divisible by p:The statements 1. to 3. are obvious from the definition, 4. is called the Completion Theorem, and 5. is the famous Law of Quadratic Reciprocity for which Gauss himself gave no less than six different proofs in the "Disquisitiones Arithmeticae". Knowing these facts, one can calculate all possible Legendre ymbols as in the following example:
Input
The first line contains the number of scenarios.
For each scenario, there is one line containing the integers a and p separated by a single blank, where 2 < p < 109 is an odd prime, and a satisfies both a !≡ 0 (mod p) and |a| <= 109.
Output
Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing (a/p), followed by a blank line.
Sample Input
3
29 79
2 29
1 3
Sample Output
Scenario #1:
-1
Scenario #2:
-1
Scenario #3:
1
Source
TUD Programming Contest 2003, Darmstadt, Germany
题目类型:平方剩余
算法分析:直接使用欧拉判定条件判断即可,注意输入中的a可能是负值,所以在使用整数快速幂取模时要注意先对底数取模,使其转化成正值!!!
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 |
#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 = 1e9 + 7; const double EPS = 1e-6; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; long long mod_f (long long a, long long b, long long mod) { long long res = 1, tt = a % mod; if (tt < 0) tt += mod; while (b) { if (b & 1) res = res * tt % mod; tt = tt * tt % mod; b >>= 1; } return res; } int main() { // CPPFF; long long a, p, t, flag = 1; cin >> t; while (t--) { cin >> a >> p; long long ans = mod_f (a, (p - 1) / 2, p); cout << "Scenario #" << flag++ << ": " << endl; if (ans == 1) cout << ans << endl; else cout << "-1" << endl; cout << endl; } return 0; } |
- « 上一篇:poj1804
- poj1811:下一篇 »