P10117 最硬核的题解【[LMXOI Round 1] Dreamer】
Bingxiu
·
·
题解
别人的解法都好强啊，各种积性函数的做法，这里来一个完全暴力的赛场上推挂 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;
}