背景

没想到自己高二时出的题目，居然真的有一天能被搬上正式比赛。
难度不高，没有用到什么高深算法，自以为是一道不错的签到题。

题目

题目描述

在这道题中，我们定义一个新的运算符号 $\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

输入 #1

3 7
11
45
14

输出 #1

4
1
2

输入输出样例 #2

输入 #2

2 10007
1919
810

输出 #2

3152
3679

解析

思路

高二时出的题目，恍惚间已经四年了啊。

记 $f(n)$ 为题目意义下 $n!\oplus p$ 的结果。注意到 $p$ 很小，可以预处理出 $k!$ 对 $p$ 常规意义下取模的结果 $g(k)$，其中 $1\le k<p$.

考虑 $1,2,3,\ldots,n$ 的组成，按照是否是质数 $p$ 的倍数分为两类。

记 $k=n\bmod p$.

首先考虑不为 $p$ 的倍数的那些数的贡献，由于这些数都不是质数 $p$ 的倍数，他们相乘的结果自然也不是 $p$ 的倍数，直接相乘取模即可。

注意到这些数对 $p$ 取模的结果由$\lfloor \frac{n}{p}\rfloor$ 组 $\{1,2,3,\ldots,p-1\}$ 与一组 $\{1,2,3,\ldots,n\bmod p\}$ 组成，因此贡献就是 $g(p-1)^{\lfloor \frac{n}{p}\rfloor}g(n\bmod p)$，这个值用快速幂可以直接算出来，最后乘到答案上就行。

然后考虑 $p$ 的倍数们的贡献，按照定义，对于其中的每一个数，我们都先让他除以 $p$，不然正常取模就是 $0$ 了。也就是说，$\{p,2p,3p,\cdots,\lfloor\frac{n}{p} \rfloor p\}$ 的贡献，完全等价于 $\{1,2,3,\cdots,\lfloor\frac{n}{p} \rfloor\}$ 的贡献，那么这个值不正是 $f(\lfloor\frac{n}{p} \rfloor)$ 吗，我们要解决的问题转化为了一个形式完全一致，但规模只有原先 $\frac{1}{p}$ 的子问题，递归解决即可。

复杂度 $O(p+T\log n)$.

代码

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1000005;
int T, p, fac[maxn];
long long n;
long long power(long long x, long long k) {
	long long ans = 1;
	while(k) {
		if(k & 1) ans = ans * x % p;
		x = x * x % p;
		k >>= 1;
	}
	return ans;
}
int solve(long long n) {
	if(n < p) return fac[n];
	return power(fac[p-1], n/p) * fac[n%p] % p * solve(n/p) % p;
}
int main() {
	cin >> T >> p;
	fac[0] = 1;
	for(int i = 1; i < p; ++i)
		fac[i] = (long long)fac[i-1] * i % p;
	while(T--) {
		cin >> n;
		cout << solve(n) << endl;
	}
}

p.s

由威尔逊定理 $(p-1)!\equiv -1\pmod p$ 可知 $g(p-1)=-1$，这样就只用考虑 $-1$ 的多少次方而无需快速幂了。

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1000005;
int T, p, fac[maxn];
long long n, ans;
int main() {
	cin >> T >> p;
	fac[0] = 1;
	for(int i = 1; i < p; ++i)
		fac[i] = (long long)fac[i-1] * i % p;
	while(T--) {
		cin >> n;
		ans = 1;
		while(n) {
			ans = ans * fac[n%p] % p;
			if(n/p & 1) ans = p - ans;
			n /= p;
		}
		cout << ans << endl;
	}
}

此外，这个题目的点子源于一道证明题，大致写一下：

题目求，$n!$ 中去除所有素因子 $p$，求对 $p$ 取模的结果。

即 $n!$ 表示为 $p$ 进制后，从低位往高位第一个非 $0$ 数字。

为了与传统意义下的 $\text{lowbit}$ 相互区别，我们不妨把 $(x)_p$ 从低位往高位第一个非 $0$ 数字记为 $\text{lobit}(x)$.

显然，$\text{lobit(}n!)$ 与 $1,2,3,\ldots,n$ 中每个数字的 $\text{lobit}$ 有关。

更准确的说，是 $\prod_{i=1}^n\text{lobit}(i)\bmod p$.

尽管 $n$ 的可能相当大，但是 $\log_pn$ 不超过 $63$，这个 $p$ 进制数的位数很小。

我们可以考虑从低到高每一位是否作为 $\text{lobit}$ 产生贡献。

设 $(n)_p=(a_m\cdots a_2a_1a_0)_p$，其中

$a_k=\left\lfloor\frac{n}{p^k}\right\rfloor\mod p$

以最低位为例，我们发现，最低位会依次取 $1,2,...,p-1$，若干个循环后，取 $1,2,...,a_0$ 结束。

进一步的，循环回合数就是 $(a_m\cdots a_2a_1)_p$，即 $\displaystyle\lfloor n/p\rfloor$.

那么最低位作为 $\text{lobit}$ 的贡献是多少呢？

$\displaystyle{(p-1)!}^{\lfloor\frac{n}{p}\rfloor}a_0! \mod p$

$=\displaystyle(-1)^{\lfloor\frac{n}{p}\rfloor}a_0! \mod p$

则总贡献为

$\displaystyle(-1)^{\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots+\lfloor n/p^m\rfloor}a_0!a_1!\cdots a_m!\mod p$

$=\displaystyle(-1)^{\varepsilon_p{(n)}}\prod_{i=0}^m a_i!\mod p$

这个等式还是蛮有趣的。