[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

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

Sample Output

5
7

Solution

窮舉帶入，利用快速冪乘積檢驗之。

#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;
}