Jacobi symbol
Problem Description
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 introduced the following notation, called the Legendre symbol, L (a,p):
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 Jacobi symbol, J (a, n) ,is a generalization of the Legendre symbol ,L (a, p).It defines as :
1. J (a, n) is only defined when n is an odd.
2. J (0, n) = 0.
3. If n is a prime number, J (a, n) = L(a, n).
4. If n is not a prime number, J (a, n) = J (a, p1) *J (a, p2)…* J (a, pm), p1…pm is the prime factor of n.
Input
Two integer a and n, 2 < a< =106，2 < n < =106，n is an odd number.
Output
Output J (a,n)
Sample Input
3 5
3 9
3 13
Sample Output
-1
0
1
Author
alpc41
题目类型：平方剩余
算法分析：这里考察了平方剩余的雅克比标号，按照题目的描述计算即可。该题本质上就是将一个数进行素因子分解，然后对于每个素因子都用欧拉判定条件来计算值，若p | a，则(a, p) = 0。若(a, p) = 1，则答案直接乘上1，否则答案直接乘上-1。注意这里的素因子是整数n所有的素因子(含重复的)！！！
|
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 |
#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 = 1e6 + 66; long long mod_f (long long a, long long b, long long mod) { long long res = 1, tt = (a % mod + mod) % mod; while (b) { if (b & 1) res = res * tt % mod; tt = tt * tt % mod; b >>= 1; } return res; } bool prime[maxn+66]; long long primelist[maxn+66], prime_len, fac[maxn+66], fac_len; void GetPrime () { memset (prime, true, sizeof (prime)); prime_len = 0; for (long long i = 2; i <= maxn; i++) { if (prime[i]) primelist[prime_len++] = i; for (long long j = 0; j < prime_len; j++) { if (i * primelist[j] > maxn) break; prime[i*primelist[j]] = false; if (i % primelist[j] == 0) break; } } } void GetFactor (long long val) { fac_len = 0; long long tt = (long long) sqrt (val + 0.0); for (long long i = 0; i < prime_len; i++) { if (primelist[i] > tt) break; while (val % primelist[i] == 0) { fac[fac_len++] = primelist[i]; val /= primelist[i]; } } if (val > 1) fac[fac_len++] = val; } int main() { // CPPFF; GetPrime (); long long a, n; while (cin >> a >> n) { GetFactor (n); long long res = 1, tt; for (long long i = 0; i < fac_len; i++) { //cout << fac[i] << endl; if (a % fac[i] == 0) { res *= 0; continue ; } tt = mod_f (a, (fac[i] - 1) / 2, fac[i]); if (tt == 1) res *= tt; else { res *= -1; } } cout << res << endl; } return 0; } |
- « 上一篇：hdu3579
- hdu4472：下一篇 »