[Tmt514] Beverage Cup 2 Warmup A - Euler's Criterion

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

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$ 有多少組合法解。

Sample Input

1
2
3
4
5
2
4
3 5 7 11
5
3 5 7 11 13

Sample Output

1
2
5
7

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("%d\n", ret);
}
return 0;
}