自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:54:51，当前版本为作者最后更新于2024-01-29 10:50:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

别人的解法都好强啊，各种积性函数的做法，这里来一个完全暴力的赛场上推挂 $4$ 次的解法。

（实际上已经简化过了，真正手推的时候推了这玩意的三倍长度……）

（希望管理员审核的时候能有耐心审核 $\LaTeX$。）

（感谢管理员 @lvkaiyi0811 十分耐心地把 $\LaTeX$ 完整地审核了一遍！！！）

首先是一些定义：

令 $g(x)$ 表示 $i_1=x,i_k=1$ 时 $i_2,\dots,i_{k-1}$ 的种类数；

令 $r(x)$ 表示 $x$ 的无平方因子（比如 $r(2^4 \times 3^5 \times 7)=2 \times 3 \times 7$）；

令 $pr(x)$ 表示 $x$ 的不同质因子数量；

令 $f(i)=i^2\prod\limits_{p|i,p \in \mathbb{P}}(1-\frac{1}{p^2})$，下面默认 $p \in \mathbb{P}$。

下面开始推式子：

$ \begin{aligned} \text{原式} &=\sum\limits_{i_k|n}\sum\limits_{i_1|\frac{n}{i_k}}f(i_k)i_1i_k^2\mu^2(i_1)g(i_1)\text{（这里认为} i_1 \gets \frac{i_1}{i_k}\text{）}\\ &=\sum\limits_{i_k|n}f(i_k)i_k^2\sum\limits_{i_1|r(\frac{n}{i_k})}i_1g(i_1)\\ &=\sum\limits_{i|n}f(i)i^2\sum\limits_{i_1|r(\frac{n}{i})}i_1(k-1)^{pr(i_1)}\\ &=\sum\limits_{i|n}i^4(\prod\limits_{p|i}(1-\frac{1}{p^2}))(\sum\limits_{i_1|r(\frac{n}{i})}i_1(k-1)^{pr(i_1)})\\ &=\sum\limits_{i|n}i^4(\prod\limits_{p|i}(1-\frac{1}{p^2}))(\prod\limits_{p|r(\frac{n}{i})}(1+p(k-1)))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{i|n}([r(\frac{n}{i})=s]i^4\prod\limits_{p|r(i)}(1-\frac{1}{p^2}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{i|\frac ns}([r(\frac{n}{i})=s]i^4\prod\limits_{p|r(i)}(1-\frac{1}{p^2}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{w|r(\frac ns)}(\sum\limits_{i|\frac ns}([r(\frac{n}{i})=s][r(i)=w]i^4\prod\limits_{p|r(i)}(1-\frac{1}{p^2})))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{w|r(\frac ns)}(\prod\limits_{p|w}(1-\frac{1}{p^2})\sum\limits_{i|\frac ns}([r(\frac{n}{i})=s][r(i)=w]i^4))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{\frac{r(n)}{s}|w|r(\frac ns)}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|w}([p_i|s]\sum\limits_{f=1}^{\alpha_i-1}p_i^{4f}+[p_i\nmid s]p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{\frac{r(n)}{s}|w|r(\frac ns)}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w,s)}(\sum\limits_{f=1}^{\alpha_i-1}p_i^{4f})\prod\limits_{p_i|\frac{w}{\gcd(w,s)}}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{\frac{r(n)}{s}|w|r(\frac ns)}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w,s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{w}{\gcd(w,s)}}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{w|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w\times \frac{r(n)}{s}}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w\times \frac{r(n)}{s},s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{w\times \frac{r(n)}{s}}{\gcd(w\times \frac{r(n)}{s},s)}}(p_i^{4\alpha_i}))\text{（这里认为} w \gets \frac{w}{\frac{r(n)}{s}}\text{）}\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\sum\limits_{w|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\frac{r(n)}{s}}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w,s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\gcd(\frac{r(n)}{s},s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{w}{\gcd(w,s)}}(p_i^{4\alpha_i})\prod\limits_{p_i|\frac{\frac{r(n)}{s}}{\gcd(\frac{r(n)}{s},s)}}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(\frac{r(n)}{s},s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{\frac{r(n)}{s}}{\gcd(\frac{r(n)}{s},s)}}(p_i^{4\alpha_i})\sum\limits_{w|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w,s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{w}{\gcd(w,s)}}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\frac{r(n)}{s}}(p_i^{4\alpha_i})\sum\limits_{w|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w,s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{w}{\gcd(w,s)}}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((1-\frac{1}{p_i^2})p_i^{4\alpha_i})\sum\limits_{w|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w,s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{w}{\gcd(w,s)}}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((p_i^2-1)p_i^{4\alpha_i-2})\sum\limits_{w|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w}(1-\frac{1}{p_i^2})\prod\limits_{p_i|\gcd(w,s)}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|\frac{w}{\gcd(w,s)}}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((p_i^2-1)p_i^{4\alpha_i-2})\sum\limits_{w_1|\frac{\frac{r(\frac ns)}{\frac{r(n)}{s}}}{\gcd(\frac{r(\frac ns)}{\frac{r(n)}{s}},s)},w_2|\gcd(\frac{r(\frac ns)}{\frac{r(n)}{s}},s)}(\prod\limits_{p_i|w_1w_2}(1-\frac{1}{p_i^2})\prod\limits_{p_i|w_2}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\prod\limits_{p_i|w_1}(p_i^{4\alpha_i}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((p_i^2-1)p_i^{4\alpha_i-2})\sum\limits_{w_1|\frac{\frac{r(\frac ns)}{\frac{r(n)}{s}}}{\frac{r(\frac ns)}{\frac{r(n)}{s}}}}(\prod\limits_{p_i|w_1}(1-\frac{1}{p_i^2})\prod\limits_{p_i|w_1}(p_i^{4\alpha_i}))\sum\limits_{w_2|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w_2}(1-\frac{1}{p_i^2})\prod\limits_{p_i|w_2}(p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((p_i^2-1)p_i^{4\alpha_i-2})\sum\limits_{w_2|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w_2}((1-\frac{1}{p_i^2})p_i^4 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((p_i^2-1)p_i^{4\alpha_i-2})\sum\limits_{w_2|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(\prod\limits_{p_i|w_2}((p_i^2-1)p_i^2 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1}))\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((p_i^2-1)p_i^{4\alpha_i-2})\prod\limits_{p_i|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(1+(p_i^2-1)p_i^2 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1})\\ &=\sum\limits_{s|r(n)}(\prod\limits_{p|s}(1+p(k-1)))\prod\limits_{p_i|\frac{r(n)}{s}}((p_i^2-1)p_i^{4\alpha_i-2})\prod\limits_{p_i|\frac{r(\frac ns)}{\frac{r(n)}{s}}}(1+(p_i^2-1)p_i^2 \times \frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1}) \end{aligned} $

那么直接爆搜 $s$，搜的过程中每个因子都计算一下三个累成符号的贡献，然后搜完所有因子直接统计即可，时间复杂度 $\Theta(2^t+\sum \alpha_i)$。

如果用矩阵快速幂优化计算 $\frac{p_i^{4(\alpha_i-1)}-1}{p_i^4-1}$，可以做到 $\Theta(2^t+\sum \log \alpha_i)$。

如果运用积性函数，可以让每次搜索变成 $O(1)$，复杂度降为 $\Theta(t+\sum \log \alpha_i) \sim O(t \log \alpha)$。

优化都很好写，然而不写也能过了，就不写了，建议出一个加强版，$T=1,1 \le t \le 5 \times 10^5,1 \le p_i,\alpha_i \le 10^{18}$，等到出了加强版再写那两个优化。

AC 代码：

//sum s|r(n)(prod pi|s(1+pi*(k-1))*prod pi|r(n)/s((pi^2-1)*pi^(4ai-2))*prod pi|r(n/s)/(r(n)/s)(pi^2(pi^2-1)(pi^4(ai-1)-1)/(pi^4-1)+1))
//o(i,si)=(pi^4(ai-si)-1)/(pi^4-1)
//o(i,si)=1+pi^4+...+pi^4(ai-si-1)
//vi=pi^2(pi^2-1)o(i,1)+1
//yi=(pi^2-1)*pi^(4ai-2)
//wi=1+pi*(k-1)
//sum s|r(n)(prod pi|s(wi)*prod pi|r(n)/s(yi)*prod pi|r(n/s)/(r(n)/s)(vi))
#include<bits/stdc++.h>
using namespace std;
typedef __int128_t li;
typedef long long ll;
#define gc getchar()
inline li rd(){li x=0;char c=gc;while(c<48||c>57) c=gc;while(c>47&&c<58) x=(x<<3)+(x<<1)+(c^48),c=gc;return x;}
li T,k,m,t,p[19],a[19],u[19],v[19],y[19],w[19],ans;//π(67)=18,2*3*5*...*67*71>1e24
inline li q(li a,li b){return !b?1:b==1?a:b&1?q(a*a%m,b>>1)*a%m:q(a*a%m,b>>1);}
inline li o(li p,int a){li r=0;for(int i=0;i<=a;++i) r=(r*p+1)%m;return r;}
inline void dfs(int x,li e){
	if(x==t){
		ans+=e;
		return;
	}
	dfs(x+1,e*y[x]%m);//sx=0
	if(a[x]==1) dfs(x+1,e*w[x]%m);//sx=1
	else dfs(x+1,e*w[x]%m*v[x]%m);
}
int main(){
	T=rd();
	while(T--){
		k=rd(),m=rd(),t=rd();
		for(int i=0;i<t;++i) p[i]=rd(),a[i]=rd();
		for(int i=0;i<t;++i){
			w[i]=(1+p[i]*(k-1))%m;
			v[i]=(p[i]%m*p[i]%m*((p[i]%m*p[i]%m+m-1)%m)%m*o(p[i]%m*(p[i]%m)%m*(p[i]%m)%m*(p[i]%m)%m,a[i]-2)+1)%m;
			y[i]=((p[i]%m*p[i]%m+m-1)%m)%m*q(p[i]%m,4*a[i]-2)%m;
		}
		ans=0,dfs(0,1);
		cout<<(int)(ans%m)<<"\n";
	}
	return 0;
}