定义：对一个数n，如果不是p的倍数且模p同余于某个数的平方，则称n为模p的二次剩余，即对一个数n，求解方程$x^2\equiv n(mod\ p)$
二次剩余的作用：对于一个数n，如果要求$\sqrt{n} mod\ p$，可以看为n是否是模p的二次剩余，如果方程$x^2\equiv n(mod\ p)$有解，就会有$x\equiv \sqrt{n} (mod\ p)$，就可以用x代替$\sqrt{n}$
下面仅考虑p为奇素数的情况
定理1：对于$x^2\equiv n(mod\ p)$，能满足“n是模p的二次剩余”的n一共有$\frac{p-1}{2}$个(不包括0)，非二次剩余有$\frac{p-1}{2}$个
证明：设$u^2=a*p+n$，即$u^2\equiv n(mod\ p)$
$\because \forall t\in \mathbb{Z}，(u+t*p)^2=u^2+2*u*t*p+(t*p)^2=(a+t^2 * p + 2*u*t)*p+n$
$\therefore u^2\equiv (u+t*p)^2 (mod\ p)$
所以我们只用考虑当$x\in [0,p-1]$，满足“n是模p的二次剩余”的n一共有多少个
假设存在两个不同的数u,v带入方程，使得$u^2\equiv n(mod\ p)$，$v^2\equiv n(mod\ p)$
那么就有$u^2\equiv v^2(mod\ p)$，显然$(u^2 - v^2)\mid p$，即$(u-v)*(u+v)\mid p$
因为$u,v\in [0,p-1]$，所以$(u-v)\nmid p$，只可能u+v=p，那么这样的u，v有$\frac{p-1}{2}$对，即满足“n是模p的二次剩余”的n有$\frac{p-1}{2}$个
我们引入勒让德符号$(\frac{n}{p})$
当$p\nmid n$且n是p的二次剩余时，$(\frac{n}{p})=1$
当$p\nmid n$且n不是p的二次剩余时，$(\frac{n}{p})=-1$
当$p\mid n$时，$(\frac{n}{p})=0$
欧拉判别准则：$(\frac{n}{p})\equiv n^{\frac{p-1}{2}}(mod\ p)$，n是p的二次剩余，当且仅当$n^{\frac{p-1}{2}}\equiv 1(mod\ p)$，n不是p的二次剩余，当且仅当$n^{\frac{p-1}{2}}\equiv -1(mod p)$
证明：由费马小定理得$x^{p-1}\equiv 1(mod\ p)$一定存在解
由于$x^2\equiv n(mod\ p)$
所以$x^{p-1}\equiv (x^2)^{\frac{p-1}{2}}\equiv n^{\frac{p-1}{2}}(mod\ p)$
所以n为p的二次剩余的条件为$n^{\frac{p-1}{2}}\equiv 1(mod\ p)$
二次剩余解(x)的个数：假设存在多组解$x_0,x_1$使得$x^2\equiv n(mod\ p)$成立，于是有$x_{0}^2\equiv x_{1}^2$，移项后得$(x_0-x_1)*(x_0+x_1)\equiv 0(mod\ p)$
因为$x_0,x_1\in [0,p-1]$
当$x_0=x_1$时，$(x_0-x_1)*(x_0+x_1)\equiv 0(mod\ p)$成立
当$x_0\neq x_1$时，$(x_0+x_1)\equiv 0(mod\ p)$成立，此时只存在两个不相等的解
Cipolla定理：设a满足$\omega =a^2-n$且$\omega $是模p得非二次剩余，即$x^2\equiv \omega (mod\ p)$无解，那么$x\equiv (a+\sqrt{\omega })^{\frac{p+1}{2}}$是$x^2\equiv n(mod\ p)$的解
所以我们可以随机一个a，然后来找到一个满足条件的解
建立一个类似于“复数域”的域，定义“虚数单位”为$\omega$，然后进行求解，由于满足“n是模p的二次剩余”的n一共有$\frac{p-1}{2}$个，所以随机次数的期望为2
例题：
luogu 5491 [模板]二次剩余
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std;typedef long long ll;int T;ll n, mod, I; struct complex { ll r, i; complex (ll tr = 0 , ll ti = 0 ) : r (tr), i (ti) { } }; inline bool operator == (complex x, complex y) { return x.r == y.r && x.i == y.i; } inline complex operator * (complex x, complex y) { ll a = (x.r * y.r + I * x.i % mod * y.i) % mod; ll b = (x.i * y.r + x.r * y.i) % mod; return complex (a, b); } complex power (complex a, ll n) complex res = 1 ; while (n) { if (n & 1 ) res = res * a; a = a * a; n >>= 1 ; } return res; } bool check (ll x) return power (x, (mod - 1 ) >> 1 ) == 1 ; } void solve (ll n, ll &x, ll &xx) ll a = rand () % mod; while (!a || check ((a * a + mod - n) % mod)) a = rand () % mod; I = (a * a - n + mod) % mod; x = power (complex (a, 1 ), (mod + 1 ) >> 1 ).r; xx = mod - x; } ll pint (ll a, ll n) ll res = 1 ; while (n) { if (n & 1 ) res = res * a % mod; a = a * a % mod; n >>= 1 ; } return res; } int main () scanf ("%d" , &T); while (T--) { scanf ("%d%lld" , &n, &mod); if (0 == n) { printf ("0\n" ); continue ; } if (1 != pint (n, (mod - 1 ) / 2 )) { printf ("Hola!\n" ); continue ; } ll x = 0 , xx = 0 ; solve (n, x, xx); if (x == xx) { printf ("%lld\n" , x); continue ; } if (x > xx) swap (x, xx); printf ("%lld %lld\n" , x, xx); } return 0 ; }
zoj 3774 Power of Fibonacci
题意：求$\sum_{i=1}^{n}F_{i}^k$，$F_{i}$为斐波那契数列的第i项，模1000000009
思路：斐波那契数列的通项公式为$F_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$
令$a=\frac{1+\sqrt{5}}{2}$，$b=\frac{1-\sqrt{5}}{2}$，则$F_n=\frac{1}{\sqrt{5}}(a^n-b^n)$
$F_n^k=(\frac{1}{\sqrt{5}})^k (a^n-b^n)^k$
$(a^n-b^n)^k$二项式展开得$(a^n-b^n)^k=C_k^0(a^n)^k+C_k^1(a^n)^{k-1}(-b^n)^1+\dots +C_k^k(-b^n)^k=\sum_{r=0}^{k}(-1)^rC_k^r(a^{k-r}*b^r)^n$
将前n项相加得$res=(\frac{1}{\sqrt{5}})^k \sum_{r=0}^k\sum_{i=1}^{n}(-1)^rC_k^r(a^{k-r}*b^r)^i=(\frac{1}{\sqrt{5}})^k \sum_{r=0}^k(-1)^rC_k^r\sum_{i=1}^{n}(a^{k-r}*b^r)^i$
令$t=a^{k-r}*b^r$，$\sum_{i=1}^{n}(a^{k-r}*b^r)^i=\sum_{i=1}^{n}t^i$，为等比数列，求和后为$\frac{t*(t^n-1)}{t}$，预处理出$a^i$和$b^i$即可O(1)求出t
所以$res=(\frac{1}{\sqrt{5}})^k\sum_{i=0}^{k}(-1)^rC_k^r\frac{t*(t^n-1)}{t-1}$
根据二次剩余，$\sqrt{5}\equiv 383008016 mod\ 1000000009$，$\frac{1+\sqrt{5}}{2}\equiv 691504013 mod\ 1000000009$，$\frac{1-\sqrt{5}}{2}\equiv 308495997 mod\ 1000000009$
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std;typedef long long ll;const int N = 100010 ;const ll mod = 1000000009 ;int T, k;ll n, A[N], B[N], fac[N], inv[N]; void init () A[0 ] = B[0 ] = fac[0 ] = 1 ; for (int i = 1 ; i < N; i++) { A[i] = A[i - 1 ] * 691504013 % mod; B[i] = B[i - 1 ] * 308495997 % mod; } for (int i = 1 ; i < N; i++) fac[i] = fac[i - 1 ] * i % mod; inv[1 ] = 1 ; for (int i = 2 ; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; inv[0 ] = 1 ; for (int i = 1 ; i < N; i++) inv[i] = inv[i] * inv[i - 1 ] % mod; } ll C (int n, int m) return fac[n] * inv[m] % mod * inv[n - m] % mod; } ll power (ll a, ll n) ll res = 1 ; while (n) { if (n & 1 ) res = res * a % mod; a = a * a % mod; n >>= 1 ; } return res; } int main () init (); scanf ("%d" , &T); while (T--) { scanf ("%lld%d" , &n, &k); ll res = 0 ; for (int r = 0 ; r <= k; r++) { ll t = A[k - r] * B[r] % mod, tr = n % mod; if (1 != t) { tr = t * (power (t, n) - 1 ) % mod; tr = tr * power (t - 1 , mod - 2 ) % mod; } tr = tr * C (k, r) % mod; if (r & 1 ) res -= tr; else res += tr; res = (res % mod + mod) % mod; } ll invt = power (383008016 , mod - 2 ); res = res * power (invt, k) % mod; printf ("%lld\n" , res); } return 0 ; }
2020 Multi-University Training Contest 1 - 1005. Fibonacci Sum
题意：求$(F_{0})^k+(F_{c})^k+(F_{2*c})^k+\dots +(F_{n*c})^k$，模1000000009
思路：和上一题差不多，时间卡的很紧，需要用到欧拉降幂
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std;typedef long long ll;const ll mod = 1000000009 ;const int N = 100010 ;ll fac[N], inv[N], pa[N], pb[N], n, c, k; int T;inline void init () fac[0 ] = 1 ; for (int i = 1 ; i < N; i++) fac[i] = fac[i - 1 ] * i % mod; inv[1 ] = 1 ; for (int i = 2 ; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; inv[0 ] = 1 ; for (int i = 1 ; i < N; i++) inv[i] = inv[i] * inv[i - 1 ] % mod; } inline ll C (int n, int m) return fac[n] * inv[m] % mod * inv[n - m] % mod; } inline ll power (ll a, ll n) ll res = 1 ; while (n) { if (n & 1 ) res = res * a % mod; a = a * a % mod; n >>= 1 ; } return res; } int main () init (); scanf ("%d" , &T); while (T--) { scanf ("%lld%lld%lld" , &n, &c, &k); ll res = 0 ; pa[0 ] = pb[0 ] = 1 ; pa[1 ] = power (691504013 , c % (mod - 1 )); pb[1 ] = power (308495997 , c % (mod - 1 )); for (int i = 2 ; i <= k; i++) { pa[i] = pa[i - 1 ] * pa[1 ] % mod; pb[i] = pb[i - 1 ] * pb[1 ] % mod; } for (int r = 0 ; r <= k; r++) { ll t = pa[k - r] * pb[r] % mod; ll tn = power (t, n % (mod - 1 )); ll tr = t * (tn - 1 ) % mod * power (t - 1 , mod - 2 ) % mod; if (1 == t) tr = n % mod; if (r & 1 ) { res += mod - C (k, r) * tr % mod; res %= mod; } else { res += C (k, r) * tr % mod; res %= mod; } } ll invt = power (383008016 , mod - 2 ); res = res * power (invt, k) % mod; printf ("%lld\n" , res); } return 0 ; }
