BZOJ2186: [Sdoi2008]沙拉公主的困惑-布布扣-bubuko.com

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：

现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。

房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。

现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。

R是一个质数。

首先，我们来引出一个定理：

如果$a$与$b$互质，那么$a+b\times k$也与$b$互质。

证明和证明$gcd$的证明类似。

反过来，我们也可以用$gcd$证明：

因为$gcd(a,b)=1$，所以$gcd(a\%b,b)=1$。

因为$a\%b=a-k\times b,k\in Z$，故$gcd(a-k*b,b)=1,k\in Z$，即$a-k*b$与$b$互质。

根据这个特性，并且$n>=m$，所以可以将$n!$分成若干段，每段为$m!$。

每一段中与$m!$互质的个数都是相等的且等于$1$到$m!$中与$m!$互质的个数。

我们可以得到这样一个式子：$$ans=\frac{n!}{m!}\times \varphi(m!)$$

我们假设$p$为$m!$的质因数，很容易可以知道$p$就是所有小于$m$的素数，$r$为质因数个数。

进一步拆开，我们可以得到：

$$ans=\frac{n!}{m!}\times m!\times \frac{\prod_{i=1}^r(p_i-1)}{\prod_{i=1}^rp_i}$$

$$\Rightarrow ans=n!\times \frac{\prod_{i=1}^r(p_i-1)}{\prod_{i=1}^rp_i}$$

因为$ans$要$\mod R$，所以我们也要算$1$到$m$的逆元，在累乘$\prod_{i=1}^rp_i$，乘的是$p_i$的逆元。

有多组询问，我们得先预处理一些数据,累乘的时候要$\% R$

先$O(n)$预处理出$\varphi(i)$，阶乘，逆元，询问直接$O(1)$算答案。

记得优化时间复杂度和空间复杂度。。。

$UPDATE$：还有个问题，就是在$n>=R$时，直接输出$0$就能$AC$。

这个问题是小粉兔大佬发现的，博客链接：博客。

然而至今没有想出来怎么解决。

能过就过吧，以后想出来了在填坑。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 10000010
#define MAXM 664580
using namespace std;
int p;
int fact[MAXN],inv[MAXN],phi[MAXN];
int k=0,prime[MAXM];
bool np[MAXN];
inline int read(){
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
void make(){
    int m=MAXN-10;
    phi[1]=fact[1]=inv[1]=1;
    for(int i=2;i<=m;i++){
        fact[i]=(long long)1LL*fact[i-1]*i%p;
        if(i<p)inv[i]=(long long)1LL*(p-p/i)*inv[p%i]%p;
        if(!np[i])prime[++k]=i;
        for(int j=1;j<=k&&prime[j]*i<=m;j++){
            np[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
    for(int i=2;i<=m;i++){
        if(!np[i])phi[i]=(long long)1LL*phi[i-1]*(i-1)%p*inv[i%p]%p;
        else phi[i]=phi[i-1];
    }
}
inline long long solve(long long n,long long m){
    if(m<p&&p<=n)return 0;
    return (long long)(1LL*fact[n]*phi[m]%p);
}
int main(){
    int t=read();p=read();
    make();
    while(t--){
        int n=read(),m=read();
        printf("%lld\n",solve(n,m));
    }
    return 0;
}

BZOJ2186: [Sdoi2008]沙拉公主的困惑

Description

Input

Output

Sample Input

Sample Output