「SDOI 2008」沙拉公主的困惑

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

Description

题目链接：BZOJ 2186

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为 $[1,n!]$，但是，政府只发行编号与 $m!$ 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对 $R$ 取模后的答案即可，保证 $R​$ 是一个质数。

本题 $T$ 组数据。

数据范围：$1\le T\le 10^4$，$1\le R\le 10^9+10$，$1\le m\le n\le 10^7$

Solution

显然我们可以推导出答案为：

首先我们有如下结论：当 $\gcd(x,y)=1$ 时，$\gcd(x+ky,y)$ 也等于 $1$。这个通过 $\gcd$ 的更相减损术很容易证明。

由于题目保证了 $n\ge m$，那么我们可以把 $[1,n!]$ 分成若干段：

这样一来，每一段的答案一定是一样的。（当 $\gcd(x,m!)=1$ 时，一定有 $\gcd(x+km!,m!)=1$）。

那么我们可以变换求和上界：

很显然右侧的求和式的值为 $\varphi(m!)$。

我们根据 $\varphi(n)=x\prod \frac{p_i-1}{p_1}$ 的定义，设 $m!=\prod_{i=1}^k {p_i}^{c_i}$，可以得到：

那么我们的答案就是：

于是我们只需要线性筛对于每个 $n$ 求出 $\prod \frac{p_i-1}{p_i}$ 的值即可。

线性筛的具体通过详见代码。

时间复杂度：$O(N+T)$

Code

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
 
#include <cstdio>

const int N=1e7+5,M=N/10;
int n,R,tot,p[M],ans[N],fac[N],inv[N];
bool flg[N];

void prework(int n) {
    fac[0]=fac[1]=1,inv[0]=inv[1]=1,ans[0]=ans[1]=1;
    for(int i=2;i<=n;++i) {
        fac[i]=1LL*fac[i-1]*i%R,inv[i]=1LL*(R-R/i)*inv[R%i]%R;
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
    for(int i=2;i<=n;++i) {
        ans[i]=ans[i-1];
        if(!flg[i]) ans[i]=1LL*ans[i]*(i-1)%R*inv[i]%R;
    }
}
int main() {
    int T;
    scanf("%d%d",&T,&R);
    prework(N-5);
    while(T--) {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",1LL*fac[n]*ans[m]%R);
    }
    return 0;
}
0%