contents
Problem
日本電影《博士熱愛的算式》中，
博士只有八十分鐘的記憶，
一旦超過這個時間，
他的記憶就自動歸零，重新開始。
然而，博士卻用一個簡單的數學公式，
驗證了愛的永恆。
$$e^{i pi} + 1 = 0 \
e^{ix} = cos(x) + i sin(x) \
e^{i pi} = cos(pi) + i sin(pi) = -1$$
判斷 $a equiv x^2 (text{ mod } p)$ 中，$a$ 是否在模 $p$ 下是個平方數。則滿足
$$a^{frac{p-1}{2}} equiv x^{p-1} equiv 1 (text{ mod } p)$$
從歐拉定理 $a^{varphi (p)} equiv 1 (text{ mod } p)$ 可以推導得到上述。接著給定一個集合，分別帶入 $a$, $p$ 有多少組合法解。
1 2 3 4 5
|
2 4 3 5 7 11 5 3 5 7 11 13
|
Sample Output
Solution
窮舉帶入，利用快速冪乘積檢驗之。
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
|
#include <stdio.h> long long mpow(long long x, long long y, long long mod) { long long ret = 1; while (y) { if (y&1) ret = (ret * x)%mod; y >>= 1, x = (x * x)%mod; } return ret; } int main() { int testcase; int n, p[128]; scanf("%d", &testcase); while (testcase--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &p[i]); int ret = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; if (mpow(p[i], (p[j]-1)/2, p[j]) == 1) ret++; } } printf("%dn", ret); } return 0; }
|
近期评论