Description

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

Input

第一行为两个整数 \(T, R\).\(T\) 表示该组中测试数据数目,\(R\) 为模;

后面 \(T\) 行, 每行一对整数 \(n, m\), 见题目描述 (\(m \leq n\)) .

Output

共 \(T\) 行, 对于每一对 \(n, m\), 输出 \(1\) 至 \(n!\) 中与 \(m!\) 素质的数的数量对 \(R\) 取模后的值.

Sample Input

1 11
4 2

Sample Output

1

Data Range

对于 100% 的数据, 满足:\(1 \leq n, m \leq 10^7, R \leq 10^9+10, T \leq 10000\)

Explanation

一道直接倒 phi 函数的题目......

懒得写题解了, 直接放传送门:http://www.cnblogs.com/BLADEVIL/p/3490321.html

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
typedef pair<lli,lli> prll;
const int maxn = 10001000;

int T;
lli modr;
int fac[maxn], // Factorial of n, i.e. n!
    inv[maxn], // Inverse of n, i.e. % modr
    prime[maxn], // Primes, starting from 2
    res[maxn]; // The result to be captured
bool vis[maxn];

prll ext_gcd(lli a, lli b)
{
    if (b == 0)
        return make_pair(1ll, 0ll);
    prll r = ext_gcd(b, a % b);
    return make_pair(r.second, r.first - a/b * r.second);
}

lli inverse(lli t)
{
    prll r = ext_gcd(t, modr);
    return (r.first % modr + modr) % modr;
}

int main(int argc, char** argv)
{
    scanf("%d%lld", &T, &modr);
    // Pre-generating factorials
    fac[1] = 1;
    for (int i = 2; i < maxn; i++)
        fac[i] = (lli)fac[i - 1] * i % modr;
    // Generating inverse and primes
    inv[1] = 1;
    for (int i = 2; i < maxn; i++) {
        if (!vis[i]) {
            prime[++prime[0]] = i;
            inv[i] = inverse(i);
        }
        for (int j = 1; j <= prime[0]; j++) {
            int x = prime[j];
            if (i * x > maxn)
                break;
            vis[i * x] = true;
            if (i % x == 0)
                break;
        }
    }
    // Now filtering the answers
    res[1] = 1;
    for (int i = 2; i <= maxn; i++) {
        res[i] = res[i - 1];
        if (!vis[i])
            res[i] = (lli)res[i] * (i-1) % modr * inv[i] % modr;
    }
    // Answering queries
    for (int i = 1; i <= T; i++) {
        int n, m;
        scanf("%d%d", &n, &m);
        lli lr = (lli)fac[n] * res[m] % modr;
        printf("%lld\n", lr);
    }
    return 0;
}