题解：P11417 [Sloi 2024]D1T1 精卫
lailai0916
·
·
题解
题意简述
积性函数 f 满足：
f(p^k)=p^{2k}+k
定义：
g(x)=\prod_{d\mid x}f(d)\bmod(10^9+7)
求 g(1),g(2),\dots,g(n) 的异或和。
解题思路
先推导加入一个新质因子的转移。
设 \gcd(x,y)=1。
每个 xy 的因数都能唯一写成 d_1d_2，
其中 d_1\mid x 且 d_2\mid y。
利用 f 的积性可得：
g(xy)=g(x)^{\tau(y)}g(y)^{\tau(x)}
其中 \tau(x) 表示 x 的因数个数。
对质数幂单独计算：
g(p^e)=\prod_{j=1}^e(p^{2j}+j)
若 p\nmid x，则转移为：
g(xp^e)=g(x)^{e+1}g(p^e)^{\tau(x)}
如果为每个整数保存答案，
空间会超过题目的 50 MiB 限制。
因此，按最大质因子拆成两类处理。
固定 B=7200。
它严格大于 \sqrt{5\times10^7}。
第一类整数的所有质因子都不超过 B。
按质因子严格递增的顺序搜索标准分解。
搜索状态记录当前整数 x、
下一层只选择编号更大的质数。
同一质数的指数在当前层依次增加。
所以，每个第一类整数会被生成恰好一次。
生成后即可把 $g(x)$ 计入异或和。
转移中最频繁的运算是：
$$
g(p^e)^{\tau(x)}
$$
相同的 $p,e$ 会搭配不同的 $\tau(x)$。
直接快速幂会产生大量重复计算。
对每个出现过的底数 $z=g(p^e)$，
把指数按五个二进制位分块。
写成 $d=a+32b$，其中 $0\le a<32$。
于是：
$$
z^d=z^a(z^{32})^b
$$
分别预处理 $z^0$ 到 $z^{31}$，
以及 $(z^{32})^0,(z^{32})^1,\dots$。
之后每次幂运算只需一次乘法。
这里不依赖精确的最大因数个数。
由因数成对出现可知：
$$
\tau(x)\le2\sqrt x<14400
$$
代码准备 $512$ 个高位块，
可以覆盖所有可能的指数。
幂表只为实际存在的质数幂分配空间。
因此，内存远小于按三维上界开整张缓存。
第二类整数含有大于 $B$ 的质因子 $p$。
由于 $B^2>n$，这样的质因子只能有一个，
且指数只能是 $1$。
所以，这类整数能唯一写成 $xp$，其中：
$$
x\le\frac{n}{p}<B
$$
对应答案为：
$$
g(xp)=g(x)^2(p^2+1)^{\tau(x)}
$$
搜索第一类整数时，
额外保存 $x\le B$ 的 $g(x)^2$ 与 $\tau(x)$。
对每个大质数 $p$，令 $z=p^2+1$。
先预处理 $z$ 的连续幂，
最高只需到 $x\le n/p$ 内的最大 $\tau(x)$。
之后枚举全部可行的 $x$ 即可。
最后还需识别所有大质数。
使用位集标记合数。
任意不超过 $n$ 的合数都有质因子不超过 $\sqrt n$。
而 $B>\sqrt n$，所以筛到 $B$ 已经足够。
筛法与大质数枚举的总耗时近似线性。
整体时间复杂度为 $O(n\log\log n)$。
空间主要由合数位集和实际质数幂的幂表构成。
在最大数据下约为 $12$ MiB。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=50000005;
const int B=7200;
const int P=920;
const int E=26;
const int L=32;
const int H=512;
const int D=L*H;
const int mod=1000000007;
vector<int> pri;
vector<array<int,L>> lo;
vector<array<int,H>> hi;
bitset<N> vis;
int id[P][E];
int g[B+5],tau[B+5],mx[B+5],pw[D];
int n,tot,cnt,ans;
int get(int p,int e,int d,int x)
{
int &z=id[p][e];
if(!z)
{
z=++cnt;
lo[z][0]=hi[z][0]=1;
for(int i=1;i<L;i++)lo[z][i]=(ll)lo[z][i-1]*x%mod;
int v=(ll)lo[z][L-1]*x%mod;
for(int i=1;i<H;i++)hi[z][i]=(ll)hi[z][i-1]*v%mod;
}
return (ll)lo[z][d&(L-1)]*hi[z][d>>5]%mod;
}
void dfs(int p,int x,int v,int d)
{
ans^=v;
if(x<=B)
{
g[x]=(ll)v*v%mod;
tau[x]=d;
}
for(int i=p;i<tot;i++)
{
int q=pri[i];
if((ll)x*q>n)break;
int y=x,z=1,h=1,cur=v;
for(int j=1;(ll)y*q<=n;j++)
{
y*=q;
h=(ll)h*q%mod*q%mod;
z=(ll)z*(h+j)%mod;
cur=(ll)cur*v%mod;
dfs(i+1,y,(ll)cur*get(i,j,d,z)%mod,d*(j+1));
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
int m=min(n,B);
for(int i=2;i<=m;i++)
{
if(vis[i])continue;
pri.push_back(i);
for(int j=i*i;j<=n;j+=i)vis[j]=1;
}
tot=pri.size();
int num=1;
for(int p:pri)
{
for(ll v=p;v<=n;)
{
num++;
if(v>n/p)break;
v*=p;
}
}
lo.resize(num);
hi.resize(num);
dfs(0,1,1,1);
for(int i=1;i<=m;i++)mx[i]=max(mx[i-1],tau[i]);
for(int i=B+1;i<=n;i+=2)
{
if(vis[i])continue;
int z=((ll)i*i+1)%mod;
int lim=n/i;
pw[0]=1;
for(int j=1;j<=mx[lim];j++)pw[j]=(ll)pw[j-1]*z%mod;
for(int j=1;j<=lim;j++)ans^=(ll)g[j]*pw[tau[j]]%mod;
}
cout<<ans<<'\n';
return 0;
}
```