2023 年华中科技大学程序设计竞赛新生赛

F - 新取模运算

https://www.luogu.com.cn/problem/P9774?contestId=138479

题目

在这道题中，我们定义一个新的运算符号 $\oplus$ 并将其称为新取模运算。

当计算 $x \oplus y$ 时，如果 $x$ 不是 $y$ 的倍数，则得到 $x$ 除以 $y$ 的余数; 否则令 $x$ 不断除以 $y$ 直到 $x$ 不再是 $y$ 的倍数，假设它为 $x'$，然后得到 $x'$ 除以 $y$ 的余数。例如，$4\oplus 5=4$，$20\oplus 5=4$，$100\oplus 5=4$。

给定一个质数 $p$，接下来会有多组询问，对于每次询问会给出一个整数 $n$，你需要计算出 $n!\oplus p$ 的值。其中 $n!$ 是 $n$ 的阶乘，即所有小于等于 $n$ 的正整数的乘积。

输入

第一行包含两个整数 $T\ (1\le T\le 10^5)$ 和 $p\ (2\le p\le 10^6)$，分别表示询问的次数和给定的质数。

接下来 $T$ 行，每行包含一个整数 $n\ (1\le n\le 10^{18})$，含义如题目所述。

输出

对于每次询问，输出一行包含一个整数，即 $n!\oplus p$ 的值。

样例

样例输入 #1

3 7
11
45
14

样例输出 #1

4
1
2

样例输入 #2

2 10007
1919
810

样例输出 #2

3152
3679

题解

根据取模的性质：

$$ (a\times b)\bmod p=(a\bmod p)\times(b\bmod p)\bmod p $$

那么对于 $n!\oplus p$，就可以把 $0\sim n$ 堆叠起来：

模 $p$ 为 $0$模 $p$ 为 $1$$\dots$模 $p$ 为 $p - 1$
$0$$1$$\dots$$p - 1$
$p$$p + 1$$\dots$$2p - 1$
$2p$$2p + 1$$\dots$$3p - 1$
$\vdots$$\vdots$ $\vdots$
$(k - 1) p$$(k-1) p + 1$$\dots$$kp - 1$
$kp$$kp+1$$\dots n$

其中，$k$ 的具体值可以计算出来为 $\lfloor\frac{n}{p}\rfloor$

我们分块来考虑：

  • 除最左侧一列外的剩余部分

    • 除最下面一行外的剩余部分：$[(p-1)!]^{k}$
    • 最下面的一行：$(n\bmod p)!$

  • 最左侧的一列

    • 将 $p$ 除掉后剩余内容为 $k!$，递归进行计算。

预处理出 $1\sim p-1$ 的阶乘值，再使用快速幂计算幂次，复杂度为 $O(p+\log n)$ 可以接受

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MAXN = 1e6 + 10;
int fact[MAXN];
int n, p;

int bpow(int a, int b)
{
    a %= p;
    int ans = 1;
    while (b)
    {
        if (b % 2)
            ans = ans * a % p;
        a = a * a % p;
        b /= 2;
    }
    return ans;
}

void init_fact()
{
    fact[0] = fact[1] = 1;
    for (int i = 2; i < p; i++)
        fact[i] = fact[i - 1] * i % p;
}

int calc(int n)
{
    if (n == 0)
        return 1;
    int ans = bpow(fact[p - 1], n / p) * fact[n % p] % p;
    return calc(n / p) * ans % p;
}

void solve()
{
    cin >> n;
    cout << calc(n) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t >> p;
    init_fact();
    while (t--)
        solve();
    return 0;
}