给出两个整数n和m,求

\sum_{i=1}^{n!}gcd(m!,i)==1

链接

洛谷

BZOJ2186

题解

显然,答案可以分为两部分计算:

Ans=\phi(m!)+\sum_{i=m!+1}^{n!}gcd(m!,i)==1

前一部分很好计算,对于后一部分,考虑到

gcd(x,m!)=1

则有

gcd(x-m!,m!)=1,...,gcd(x-k*m!,m!)=1

所以,答案的最终形式为

Ans=\phi(m!)\frac{n!}{m!}

令

f(x)=\frac{\phi(x!)}{x!}

化简得

f(x)=\Pi_{i=1}^{r}(1-\frac{1}{p_{i}})

而这个函数是可以递推计算的.所以先预处理出f,然后对于每个询问操作直接输出即可.

注意这道题卡内存,必须开int.

辣鸡BZOJ评测机,卡我常数

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 10000010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

LL T,MOD,n,m,i,Ans;
int inv[N],f[N],mi[N];
bool v[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline LL read(){
    LL p=0; char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Inv(){
    LL i=0;
    inv[1]=1;
    for (i=2;i<=10000000;i++)   inv[i]=(LL)inv[MOD%i]*(MOD-MOD/i)%MOD;
}

inline void Ready(){
    LL i=0,x=0;
    for (i=2;i<=10000000;i++){
        if (v[i])   continue;
        for (x=i*i;x<=10000000;x+=i)    v[x]=1;
    }
    mi[1]=f[1]=1;
    for (i=2;i<=10000000;i++)
        f[i]=(v[i])?f[i-1]:((((LL)f[i-1]*(i-1))%MOD)*(LL)inv[i])%MOD;
    for (i=2;i<=10000000;i++)   mi[i]=((LL)mi[i-1]*i)%MOD;
}

int main(){
    T=read();   MOD=read();
    Inv();  Ready();
    while (T--){
        n=read();   m=read();
        Ans=((LL)f[m]*mi[n])%MOD;
        printf("%lld\n",Ans);
    }
    return 0;
}