[ICPC 2019 Nanchang Invitational Online G]tsy’s number

这几周很忙…好久没有静心做点题了。。
北理校赛的期望DP题做不对
南昌网赛的积性函数题不会做
各种专题都有待加强
这几天先再看看数论吧。

Link

Solution

首先

\begin{aligned}
&\frac{\varphi(i)\varphi(j^2)\varphi(k^3)}{\varphi(i)\varphi(j)\varphi(k)}\\
=&\frac {j^2\prod_{p|j^2}(1-\frac 1p)k^3\prod_{p|k^3}(1-\frac 1p)}
{j\prod_{p|j}(1-\frac 1p)k\prod_{p|k}(1-\frac 1p)}\\
=&jk^2
\end{aligned}

式子化为

\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^njk^2\varphi((i,j,k))\\
=&\sum_{d}\varphi(d)\sum_{i=1}^{[\frac nd]}\sum_{j=1}^{[\frac nd]}\sum_{k=1}^{[\frac nd]}
(jd)(kd)^2[(i,j,k)=1]\\
=&\sum_{d}d^3\varphi(d)\sum_{i=1}^{[\frac nd]}\sum_{j=1}^{[\frac nd]}\sum_{k=1}^{[\frac nd]}
jk^2[(i,j,k)=1]\\
=&\sum_{d}d^3\varphi(d)\sum_{i=1}^{[\frac nd]}\sum_{j=1}^{[\frac nd]}\sum_{k=1}^{[\frac nd]}
jk^2\sum_{t|i,t|j,t|k}\mu(t)\\
=&\sum_{d}d^3\varphi(d)\sum_{t}t^3\mu(t)\sum_{i=1}^{[\frac n{dt}]}\sum_{j=1}^{[\frac n{dt}]}\sum_{k=1}^{[\frac n{dt}]}jk^2\\
=&\sum_{T}T^3\sum_{d|T}\varphi(d)\mu(\frac Td)\sum_{i=1}^{[\frac nT]}\sum_{j=1}^{[\frac nT]}\sum_{k=1}^{[\frac nT]}jk^2\\
=&\sum_{T}T^3\sum_{d|T}\varphi(d)\mu(\frac Td)[\frac nT](\sum_{j=1}^{[\frac nT]}j)(\sum_{k=1}^{[\frac nT]}k^2)
\end{aligned}

考虑筛出T^3(\varphi*\mu)(T)的前缀和。
都是积性函数,随便筛的。

\begin{aligned}
&(p^t)^3(\mu * \varphi)(p^t)\\
=&p^{3t}\sum_{d|p^t}\mu(d)\varphi(\frac {p^t}d)\\
=&p^{3t}(\mu(1)\varphi(p^t)+\mu(p)\varphi(p^{t-1}))\\
=&p^{3t}(\varphi(p^t)-\varphi(p^{t-1}))\\
\end{aligned}

Code

线性筛也写的不熟,写一次忘一次。

#include <bits/stdc++.h>

const int N=1e7,XN=N+11;

unsigned int Sum(unsigned int x) {
    return (long long)x*(x+1)/2;
}

unsigned int Sum2(unsigned int x) {
    return (unsigned long long)x*(x+1)%(6ull<<30)*(2*x+1)%(6ull<<30)/6;
}

unsigned int Pow3(unsigned int x) {
    return x*x*x;
}

unsigned int g[XN];
void Prep() {
    static bool notPrime[XN];
    static struct { int p,pt; }mp[XN];
    static int prime[XN],pcnt;

    g[1]=1;

    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
            mp[i]={i,i};
            g[i]=Pow3(i)*(i-2);
        }
        for(int j=1,x;j<=pcnt && prime[j]<=mp[i].p && (x=i*prime[j])<=N;++j) {
            notPrime[x]=1;
            if(mp[i].p==prime[j])
                mp[x]={prime[j],mp[i].pt*prime[j]};
            else
                mp[x]={prime[j],prime[j]};
            auto Phi=[&](int pt)->int {
                return pt==1?1:(mp[x].p-1)*(pt/mp[x].p);
            };
            g[x]=g[x/mp[x].pt]*Pow3(mp[x].pt)*(Phi(mp[x].pt)-Phi(mp[x].pt/mp[x].p));
        }
    }
    for(int i=1;i<=N;++i)
        g[i]+=g[i-1];
}

void Work() {
    int n;std::cin>>n;
    unsigned int Ans=0;
    for(int l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        Ans+=(n/l)*Sum(n/l)*Sum2(n/l)*(g[r]-g[l-1]);
    }
    std::cout<<(Ans%(1<<30))<<'\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    //freopen("input","r",stdin);
    Prep();
    /*
    for(int i=1;i<=100;++i)
        std::cerr<<Sum(i)-Sum(i-1)<<' '<<Sum2(i)-Sum2(i-1)<<'\n';
    */
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注