「HDU 5391」Zball in Tina Town

Description

题目链接:HDU 5391

一个球初始体积为 $1$,一天天变大,第一天变大 $1$ 倍,第二天变大 $2$ 倍,第 $n$ 天变大 $n$ 倍……问当第 $n−1$ 天的时候,体积变为多少。答案对 $n​$ 取模。

本题 $T$ 组数据。

数据范围:$1\le T\le 10^5$,$2\le n\le 10^9$


Solution

显然题目让我们求的是:

看似无从下手,我们有这么一个神奇的定理:威尔逊定理

考虑如何证明

  • 当 $p=2​$ 时式子显然成立。
  • 当 $p>2$ 时,由于每个数逆元的唯一性,当 $ab\equiv 1\pmod p$ 时,$a$ 和 $b$ 互为逆元。因此在 $[2,p-2]$ 中可以两两配对互为逆元。故 $(p-1)!\equiv -1\pmod p$。
  • 很显然这个式子在 $n\not\in\text{prime}$ 时答案为 $0$。

当然这个定理有一个小坑点:当 $n=4$ 时答案为 $2$!

时间复杂度:$O(T\sqrt n)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>

bool check(int n) {
for(int i=2;i*i<=n;++i) if(n%i==0) return 0;
return 1;
}
int main() {
int T;
for(scanf("%d",&T);T--;) {
int n;
scanf("%d",&n);
if(!check(n)) puts("0");
else printf("%d\n",n-1);
}
return 0;
}
0%