【题解】SDOI2008莎拉公主的困惑

挺有趣的恩：洛谷P2155

在纸上打打草稿，写出n!个数，从先往后，遇到不互质的就筛掉——发现一个奇妙的性质！：筛掉的次数、顺序好像是周期性出现的呢~

而且更加妙妙的是，好像还是m!一轮..那么因为n!一定能被m!整除，所以问题转变为：（n!\m! - 有多少个循环节）*(φ(m))。

接下来，φ(m) = m!*(1 - 1/p1)*(1 - 1/p2)...任务就只剩下打出阶乘表&逆元啦。离线的处理会快很多。

#include <bits/stdc++.h>

using namespace std;

#define maxn 10000050

#define ll long long

#define int long long

int maxx, now = , P, T, tot, inv[maxn], ans[], pri[maxn],fac_a[maxn], fac_b[maxn], fac_c[maxn];

bool is_prime[maxn];

struct query

{

    int n, m, id, pri;

}Q[];

int read()

{

    int x = ;

    char c;

    c = getchar();

    while(c < '' || c > '') c = getchar();

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x;

}

bool cmp1(query a, query b)

{

    return a.m < b.m;

}

int Get_Pri(int n)

{

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

    {

        if(!is_prime[i])

        {

            pri[++ tot] = i;

            while(now <= T && pri[tot] > Q[now].m)

            {

                Q[now].pri = tot - ;

                now ++;

            }

        }

        while(now <= T && i == n)

            {

                Q[now].pri = tot;

                now ++;

            }

        for(int j = ; j <= tot; j ++)

        {

            if(i * pri[j] > n) break;

            is_prime[i * pri[j]] = ;

            if(!(i % pri[j])) break;

        }

    }

}

int Get_fac(int n)

{

    fac_a[] = fac_a[] = fac_b[] = fac_b[] = fac_c[] = fac_c[] = ;

    inv[] = inv[] = ;

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

     {

         fac_a[i] = (fac_a[i - ] * i) % P;

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

    }

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

    {

        fac_b[i] = inv[pri[i]];

        fac_b[i] = (fac_b[i] * fac_b[i - ]) % P;

        fac_c[i] = pri[i] - ;

        fac_c[i] = (fac_c[i] * fac_c[i - ]) % P;

    }

}

signed main()

{

    T = read(), P = read();

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

    {

        Q[i].n = read(), Q[i].m = read(), Q[i].id = i;

        maxx = max(maxx, max(Q[i].n, Q[i].m));

    }

    sort(Q + , Q +  + T, cmp1);

    Get_Pri(maxx);

    Get_fac(maxx);

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

        ans[Q[i].id] = ((fac_a[Q[i].n] * fac_b[Q[i].pri]) % P * fac_c[Q[i].pri]) % P;

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

        printf("%lld\n", ans[i]);

    return ;

}