题解：P11417 [Sloi 2024]D1T1 精卫

Polarisx · 2024-12-21 14:50:32 · 题解

题目传送门。

思路

推式子，考虑从 g(x) 推到 g(x\times p^c),(p\bot x,p\in\mathbb{P})，有

空间只有 50MB，线性筛显然是行不通的，考虑枚举素数来获得合数，搜索过程中记录一下需要的值即可，但是我们发现 g(p^c)^{\sigma_0(x)} 无法简单得到，因此时间复杂度必定带个 \log。

考虑空间换时间，5e7 的数组显然开不下，考虑分成两批来做，令 \mathrm{mxp}(n) 表示 n 的最大素因子，不妨将 [1,n] 的数分成 \mathrm{mxp}(i)\le \sqrt n 与 \mathrm{mxp}(i)>\sqrt n，对于第一批，搜索加上记忆化即可，对于第二批，由于它们至多只有一个大于 \sqrt n 的素因子，单独计算这个素因子的贡献即可。

时间复杂度可近似看成 \mathcal O (n)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Mod=1e9+7;
const int Maxm=5e7+5,B=7200;
vector<int>prm;
bitset<Maxm>isp;
int ans;
int n,sz;
int mp[960][26][352];
int g[B+5],d[B+5];

inline ll ksm(ll a,int b,int mod){
    ll z=1;
    while(b){
        if(b&1) z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}
void dfs(int p,int now,int G,int divs){
    ans^=G;
    if(now<=B){
        g[now]=1ll*G*G%Mod;d[now]=divs;
    }
    for(int i=p;i<sz;i++){
        int nz=now,nf=1,ng=1,nG=G;
        const int P=prm[i];
        if(1ll*nz*P>n) break;
        for(int c=1;;c++){
            if(1ll*nz*P>n) break;
            nz*=P; nf=1ll*nf*P%Mod*P%Mod; ng=1ll*ng*(nf+c)%Mod;
            nG=1ll*nG*G%Mod; int pw;
            if(!mp[i][c][divs]) mp[i][c][divs]=ksm(ng,divs,Mod);
            pw=mp[i][c][divs];
            dfs(i+1,nz,1ll*nG*pw%Mod,divs*(c+1));
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=2;i<=min(n,B);i++){
        if(!isp.test(i)){
            prm.emplace_back(i);
            for(int j=i+i;j<=n;j+=i) isp.set(j);
        }
    }
    sz=prm.size();
    dfs(0,1,1,1);
    for(int i=B+1;i<=n;i+=2){
        if(!isp.test(i)){
            int v=(1ll*i*i+1)%Mod;
            for(int j=1;i*j<=n;j++){
                ans^=((1ll*g[j]*ksm(v,d[j],Mod))%Mod);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}