P6788 「EZEC-3」四月樱花

· · 题解

\text{Solution}

简单题就敢于乱搞。

ans=\prod_{x=1}^{t}\prod_{y|x}\dfrac{y^{d(y)}}{\prod_{z|y}(z+1)^2} \prod_{x=1}^{t}\prod_{y|x}y^{d(y)}\prod_{z|y}\dfrac{1}{(z+1)^2}

单独处理

y^{d(y)} d(n)=\sum_{d|n}1 y^{\sum_{d|y}1} \prod_{d|y}y

我们发现 d 实际上就是原式的 z，回代。

\prod_{x=1}^{t}\prod_{y|x}\prod_{z|y}\dfrac{y}{(z+1)^2}

有 z|y，考虑 \prod_{z|y}y 能否转化为 z 的形式，就要敢于乱代。

有个东西可以有点启发

\prod_{d|n}d=\prod_{d|n}\dfrac{n}{d}

考虑构造

\prod_{z|y}z\prod_{z|y}z'=\prod_{z|y}y

有 z'=\dfrac{y}{z}

\prod_{z|y}z\prod_{z|y}\dfrac{y}{z}=(\prod_{z|y}z)^2=\prod_{z|y}y \prod_{x=1}^{t}\prod_{y|x}\prod_{z|y}\dfrac{z^2}{(z+1)^2}

枚举 y

\prod_{y=1}^{t}\prod_{y|x}\prod_{z|y}\dfrac{z^2}{(z+1)^2}

有

x \in [1,t],y|x (\prod_{y=1}^t\prod_{z|y}\dfrac{z^2}{(z+1)^2})^{\lfloor\frac{t}{y}\rfloor}

其实我一直觉得打下取整符号挺烦的 所以我不打了

枚举 z

(\prod_{z=1}^{t}\prod_{z|y}\dfrac{z^2}{(z+1)^2})^{\frac{t}{y}} ((\prod_{z=1}^{t}\dfrac{z^2}{(z+1)^2})^{\frac{t}{yz}})^{\sum_{y=1}^{\frac{t}{z}}1} (\prod_{z=1}^{t}\dfrac{z^2}{(z+1)^2})^{\sum_{y=1}^{\frac{t}{z}}\frac{t}{yz}}

指数很整除分块

记

h(n)=\sum_{i=1}^{n}\dfrac{n}{i}

指数就是

h(\dfrac{t}{z}) \prod_{z=l}^{r}\dfrac{z^2}{(z+1)^2}=\dfrac{l}{(r+1)^2}

再套个快速幂即可。

然而我以为能过的时候，却 TLE 了。

我们发现瓶颈是在 h(\dfrac{t}{z})。

h(n)=\sum_{i=1}^{n}\dfrac{n}{i}=\sum_{i=1}^{n}\sum_{j=1}^{n}[j|i]=\sum_{i=1}^{n}\sigma(i)

我们要快速求出 \sigma(i)。

预处理大法好！我们可以预处理

暴力枚举是 $O(n' \ln n'),n'=n^{\frac{2}{3}}$，足已通过本题，但是有个东西叫做狄利克雷前缀和，可以做到 $O(n \log^2 n)$ ，其中 $n$ 是$[1,n']$ 的质数数量。 目前是最优解。 这道题就被我们解决了！ ## $\text{Code} 
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>

#define ll long long
#define uint unsigned int

using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
uint urd() {
    uint sum=0; char ch=getchar();
    while(!isdigit(ch)) {ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum;
}
ll lrd() {
    ll f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
void pr(uint x) {
    if(x<0) {putchar('-');x=-x;}
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}

uint fpow(uint x,uint y,uint mod) {
    uint res=1; x%=mod;
//  cout<<x<<" "<<y<<endl;
    while(y) {
        if(y&1) res=1llu*res*x%mod;
        x=1llu*x*x%mod; y>>=1;
    }
//  cout<<res<<endl;
    return res;
}

#define N (int)(5e5+5)

bool vis[N];
int pri[N>>1],a[N],tot;
void init() {
    for(int i=2;i<N;i++) {
        if(!vis[i]) pri[++tot]=i;
        for(int j=1;j<=tot&&i*pri[j]<N;j++) {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    for(int i=1;i<N;i++) a[i]=1;
    for(int i=1;i<=tot;i++)
        for(int j=1;j*pri[i]<N;j++)
            a[j*pri[i]]+=a[j];
    for(int i=1;i<N;i++) a[i]+=a[i-1];
}

uint H(uint n,uint mod) {
    if(n<N) return a[n];
    uint ans=0;
    for(uint l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans+=(r-l+1)*(n/l);
        ans%=mod;
    }
    return ans;
}

int main() {
    init();
    uint n=urd(),mod=urd();
    uint ans=1;
    for(uint l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans=(1llu*ans*fpow(1llu*l*l%mod*fpow(1llu*(r+1)*(r+1)%mod,mod-2,mod)%mod,H(n/l,mod-1)%mod,mod))%mod;
    }
    pr(ans);
    return 0;
}