题目 | 新取模运算

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

F - 新取模运算

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

题目

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

当计算 $x\oplus y$ 时，如果 $x$ 不是 $y$ 的倍数，则得到 $x$ 除以 $y$ 的余数; 否则令 $x$ 不断除以 $y$ 直到 $x$ 不再是 $y$ 的倍数，假设它为 $x^{\prime }$，然后得到 $x^{\prime }$ 除以 $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)modp=(amodp)\times (bmodp)modp$$

那么对于 $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$
$⋮$	$⋮$		$⋮$
$(k-1)p$	$(k-1)p+1$	$\dots$	$kp-1$
$kp$	$kp+1$	$\dots n$

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

我们分块来考虑：

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

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

• 最左侧的一列

  • 将 $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;
}