威尔逊定理例题汇总

hdu 5391 Zball in Tina Town

Problem Description

Tina Town is a friendly place. People there care about each other.
Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day, it becomes 1 time as large as its original size. On the second day,it will become 2 times as large as the size on the first day. On the n-th day,it will become n times as large as the size on the (n-1)-th day. Tina want to know its size on the (n-1)-th day modulo n.

Input

The first line of input contains an integer T, representing the number of cases.
The following T lines, each line contains an integer n, according to the description.
$ T \leq 10^5,2 \leq n \leq 10^9 $

Output

For each test case, output an integer representing the answer.

Sample Input

2
3
10

Sample Output

2
0

思路：

求 $ (n-1)! \; mod \; n $。注意：特判 n = 4 时，$ ans = 2 $。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int t,n;
bool check(int x){
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0) return false;
    return true;
}
int main(){
    while(~scanf("%d", &t)){
        while(t--){
            scanf("%d", &n);
            if(n == 4) puts("2"); //特判 6 ≡ 2(mod 4)
            else if(check(n)) printf("%d\n", n - 1); //如果是素数，那么取模之后为n-1，其余情况下余数为0
            else puts("0");
        }
    }
    return 0;
}

hdu 2973 YAPTCHA

Problem Description

The math department has been having problems lately. Due to immense amount of unsolicited automated programs which were crawling across their pages, they decided to put Yet-Another-Public-Turing-Test-to-Tell-Computers-and-Humans-Apart on their webpages. In short, to get access to their scientific papers, one have to prove yourself eligible and worthy, i.e. solve a mathematic riddle.
However, the test turned out difficult for some math PhD students and even for some professors. Therefore, the math department wants to write a helper program which solves this task (it is not irrational, as they are going to make money on selling the program).
The task that is presented to anyone visiting the start page of the math department is as follows: given a natural n, compute

$$S_n = \sum_{k=1}^n \left[\frac{(3k+6)!+1}{3k+7}-\left[\frac{(3k+6)!}{3k+7}\right] \right]$$

where $ [x] $ denotes the largest integer not greater than x.

Input

The first line contains the number of queries t $ (t \leq 10^6) $. Each query consist of one natural number n $ (1 \leq n \leq 10^6) $.

Output

For each n given in the input output the value of $ S_n $.

Sample Input

13
1
2
3
4
5
6
7
8
9
10
100
1000
10000

Sample Output

0
1
1
2
2
2
2
3
3
4
28
207
1609

思路：

威尔逊定理：$ (p-1)! \equiv -1\;(mod\;p) \Leftrightarrow (p-1)!+1 \equiv 0 \;(mod\;p) $。
①当 $ 3k + 7 $ 是素数时，$ (3k+7)|[(3k+6)!+1] $，令 $ m=\frac{(3k+6)!+1}{3k+7} $，
则 $ \left [ \frac{(3k+6)!}{3k+7} \right ] = \left [ \frac{m(3k+7)-1}{3k+7} \right ] = \left [ m-\frac{1}{3k+7} \right ] = m-1 $，
此时，$ T_k = \left [ m - (m-1) \right ] =1 $；
②当 $ 3k + 7 (\ge10)$ 是合数时，由威尔逊定理的相关证明可知当 $ p > 4 $ 且p为合数时，$ (p-1)! \equiv 0 \;(mod \; p) $，令 $ m=\frac{(3k+6)!}{3k+7} $，则 $ \frac{(3k+6)!+1}{3k+7} = \frac{m(3k+7)+1}{3k+7} = m+\frac{1}{3k+7} $，
此时，$ T_k = \left [ m+\frac{1}{3k+7}-m \right ] = \left [ \frac{1}{3k+7} \right ] = 0 $。n最大只有 $ 10^6 $，预处理打表即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 50;
const int maxv = 1e6 + 5;
bool isp[maxn]; int T, n, cnt = 0, prime[maxn], ans[maxv];
void euler_sieve(){
    memset(isp, true, sizeof(isp));
    memset(prime, 0, sizeof(prime));
    isp[0] = isp[1] = false;
    for(int i = 2; i < maxn; ++i){
        if(isp[i]) prime[cnt++] = i;
        for(int j = 0; j < cnt && i * prime[j] < maxn; ++j){
            isp[i * prime[j]] = false;
            if(i % prime[j] == 0) break;
        }
    }
}
int main(){
    euler_sieve();
    memset(ans, 0, sizeof(ans));
    for(int i = 1; i < maxv; ++i){ //预处理，求1~n范围内，3 * i + 7 是素数的个数
        if(isp[3 * i + 7]) ans[i] = ans[i - 1] + 1;
        else ans[i] = ans[i - 1];
    }
    while(cin >> T){
        while(T--){
            cin >> n;
            cout << ans[n] << endl;
        }
    }
    return 0;
}