bzoj 2186

非常有趣的题

题意：求1~N！中有多少个与M！互质的数，T组询问，答案对R取模

题解：

首先，因为N>M，所以N！>M！，所以答案一定有一部分是φ（M！）

接下来做一些分析：

引理：

若x与p互质，则x+kp与p互质（k∈Z）

证明：

反证法：假设x+kp与p不互质，则设gcd(x+kp,p）=d(d!=1)，那么设p=k1d,x+kp=k2d，于是：

x=k2d-kk1d

所以x=(k2-kk1)d

那么gcd（x,p）=d

这与x与p互质相矛盾，假设不成立，原命题得证

那么，我们可以将N！分组，每组大小为M!（即将N!中每个数表示成kM！+c），那么每部分与M!互质的数的个数都是φ（M!），合起来就是N!/M!*φ（M!）

预处理即可，需要使用unsigned来卡常

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll unsigned int

#define ull unsigned long long

#define maxn 10000000

using namespace std;

ll n,m;

ll T,R;

ll inv[maxn+];

ll mul[maxn+];

ll pri[maxn+];

ll phi[maxn+];

bool used[maxn+];

int tot=;

void init()

{

    phi[]=inv[]=inv[]=mul[]=mul[]=;

    for(int i=;i<=maxn;i++)

    {

        inv[i]=(ull)(R-R/i)*inv[R%i]%R;

        if(!used[i])

        {

            pri[++tot]=i;

        }

        for(int j=;j<=tot&&i*pri[j]<=maxn;j++)

        {

            used[i*pri[j]]=;

            if(i%pri[j]==)

            {

                break;

            }

        }

    }

    for(int i=;i<=maxn;i++)

    {

        mul[i]=(ull)mul[i-]*i%R;

        inv[i]=(ull)inv[i-]*inv[i]%R;

        if(!used[i])

        {

            phi[i]=(ull)phi[i-]*(i-)%R;

        }else

        {

            phi[i]=(ull)phi[i-]*i%R;

        }

    }

}

int main()

{

    scanf("%u%u",&T,&R);

    init();

    while(T--)

    {

        scanf("%u%u",&n,&m);

        printf("%u\n",(ull)mul[n]*inv[m]%R*(ull)phi[m]%R);

    }

    return ;

}