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

Description

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

Input

第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n

Output

共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值

Sample Input

1 11
4 2

Sample Output

1

数据范围：
对于100%的数据，1 < = N , M < = 10000000

题目传送门

这题的时间复杂度真·玄学，空间开的也很神奇

一眼数论+欧拉+筛

但是还是想了很久，说说过程吧：

首先若x与y互质，则x+y与y也互质，x+2y与y也互质，这应该是初中生都知道的

然后就可以得出这个结论： φ(m!)*(n!)/(m!)%R

n，m太大得化简

那么先考虑φ(m!)，m!的所有质因数恰好就是m以内所有的质数

所以可得：φ(m!)=(m!)*∏(pi-1)/pi (pi<=m)，也是学过数论该知道的定理

再次化简：(n!)*∏(pi-1)/pi (pi<=m)%R

n!预处理出来，然后用到逆元公式

结果出来

代码如下：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
int R;
int T;
int prime[5100000],ans[10000010];
int a[10000010],tot[10000010];
bool v[10000010];
void solve()
{
    prime[0]=0;
    for(int i=2;i<=10000000;i++)
    {
        if(v[i]==false)
            prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&(ll)i*prime[j]<=10000000;j++)
        {
            v[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
    a[1]=1;
    for(int i=2;i<=10000000;i++)
        a[i]=(ll)a[i-1]*i%R;
    tot[1]=1;  
    for(int i=2;i<=10000000&&i<R;i++)  
        tot[i]=(ll)(R-R/i)*tot[R%i]%R;  
    ans[1]=1;  
    for(int i=2;i<=10000000;i++)  
    {  
        if(v[i]==false) ans[i]=(ll)ans[i-1]*(i-1)%R*tot[i%R]%R;  
        else  ans[i]=(ll)ans[i-1];  
    }  
}
int main()
{
    scanf("%d%d",&T,&R);
    solve();
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%d\n",(ll)a[n]*ans[m]%R);
    }
    return 0;
}

by_lmy

秒客网