「HDU 5391」Zball in Tina Town

发表于 | | 阅读次数:
字数统计: 312 字

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%