powerful number

· · 个人记录

由于不会min25，只能来学powerful number了。

我们称：p=\sum_{i} p_i^{k_i},\forall k_i>1的数称作powerful number。

考虑powerful number在n以内的个数。

任意一个powerful number都可以表示成a^2b^3

\begin{aligned} cnt(n) &= \sum_{a=1}^{\sqrt n} \left(\frac n {a^2} \right)^{\frac 1 3} \\ & \to \int_1^{\sqrt n} \left(\frac n {x^2}\right)^{\frac{1} 3} \\ & \to n^{\frac 1 3} \sqrt{ n^{\frac 1 3}} \\ &\to \sqrt n \end{aligned}

现在要求f(x)的前缀和。

以下p都指质数。

构造两个简单的积性函数f(x) = g(x)*h(x) 。

且g(x)的前缀和非常好求，且g(p)=f(p)。

那么根据f(p)=g(p)h(1)+g(1)h(p)=g(p)+h(p)。

可以得出h(p)=0。又因为h(p)是积性函数，所以h只在powerful number处有值。

那么

\sum_i^n f_i = \sum_j h_j \sum_{k=1}^{n/j}g(k)

显然如果h,g都知道就很好求了。

现在考虑怎么构造

具体地：g(p) = p(p-1)

显然不能直接令g(x) = x(x-1)，这不是积性的。

小小的尝试：取g(x) = x\varphi(x)

\begin{aligned} f(p^k)= p^k(p^k-1) &= \sum_{i=0}^k h(p^i)g(p^{k-i}) \\ &=(p-1)\sum_{i=0}^kh(p^i)(p^{2k-2i-1}) \\ p^k(1+p+...+p^{k-1})&=\sum_{i=0}^kh(p^i)p^{2k-2i-1} \\ 1+p+...+p^{k-1}&=\sum_{i=0}^kh(p^i)p^{k-2i-1} \\ 1+p+...+p^{k-1}&=p^{k-1}+\sum_{i=2}^kh(p^i)p^{k-2i-1} \\ 1+p+...+p^{k-2} &= \sum_{i=2}^kh(p^i)p^{k-2i-1} \\ h(p^i) &= p^{i+1} ,i\gt 1 \end{aligned}

竟然成功了，小编也很好奇。

大家一定觉得很奇怪，为什么和其他题解求出的h不同呢？原因很简单，因为我求错了。

关键就是g(p^0) =1\ne (p-1)p^{-1}

更正确的过程：

\begin{aligned} f(p^k)= p^k(p^k-1) &= h(p^k)+(p-1)\sum_{i=0}^{k-1} h(p^i)p^{2k-2i-1} \\ p^{k}(p^k-1)-p^{k-1}(p^{k-1}-1)&=h(p^k)+(p^2-p-1)h(p^{k-1})+(p-1)(p^2-1)\sum_{i=0}^{k-2}h(p^i) \\ \cdots \end{aligned}

能力有限，推不下去了。这个\sum根本化不掉啊。只能说有个题解写的过程全是错的，但是结果是对的(hah)。

既然推不出h，那就暴力算吧。反正f(p^k)和右边都知道，不知道的只有h(p^k)。

\begin{aligned} p^2(p^2-1) &= h(p^2) + p^3(p-1) \\ p^4-p^2 &= h(p^2)+p^4 -p^3 \\ h(p^2) & = p^3-p^2 \\ p^3(p^3-1) &= h(p^3)+ p(p-1)(p^3-p^2)+p^5(p-1) \\ p^6-p^3 &= h(p^3) +p^5-2p^4+p^3+p^6-p^5 \\ h(p^3) & = 2p^4-2p^3 \\ \cdots \cdots \\ h(p^k) &= (k-1)(p^{k+1}-p^k) \end{aligned}

其实是可以只把所有的h(p^k)暴力算出来的，那样不用脑子。

复习一下杜教筛。

\begin{aligned} \sum_{i=1}^n (f*g)(i) &= \sum_{i=1}^ng(i)S(n/i) \\ \text{prove:} \\ &\sum_{i=1}^n\sum_{d|i}g(d)f(i/d) \\ =&\sum_{d=1}^ng(d)S(n/d) \\ f*id =&id^2 \\ S(n)id(1) =& n(n+1)(2n+1)/6 - \sum_{i=1}^{n-1} id(i)S(n/i) \\ S(n)&= n(n+1)(2n+1)/6-\sum_{i=1}^{n-1}iS(\lfloor\frac n i\rfloor) \end{aligned}

好难得÷生题啊。

时间复杂度O(n^\frac 2 3)

破烂代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<':'<<x<<endl
const ll mod = 1e9+7,inv2 = (mod+1)/2,inv6 = (mod+1)/6;
map<ll,ll> mp;
const int N = 1e7+20;
ll xphi[N];
int prime[N],tot,tot1,cnt;bool mark[N];
ll n;
pair<ll,ll> h[N];
ll ksm(ll a,ll b=mod-2)
{
    ll ret = 1;
    for(;b;b>>=1,a=a*a%mod)if(b&1)
        ret =ret*a%mod;
    return ret;
}
void init()
{
    xphi[1] = 1;
    for(int i=2;i<N;i++)
    {
        if(!mark[i])
        {
            prime[++tot] = i;
            xphi[i] = i-1;
        }
        for(int j=1;j<=tot&&i*prime[j]<N;j++)
        {
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                xphi[i*prime[j]]=xphi[i]*prime[j];
                break;
            }
            xphi[i*prime[j]]=xphi[i]*xphi[prime[j]];
        }
    }
    for(int i=1;i<N;i++)
        xphi[i]=(xphi[i]*i+xphi[i-1])%mod;
}
void dfs(int k,ll val,ll x)
{
    if(k>tot1 || x*prime[k] > n)
    {
        h[++cnt]={x,val};
        return ;
    }
    dfs(k+1,val,x);
    x*=prime[k];
    for(int i=2;i<=n&&x*prime[k]<=n;i++)
    {
        x*=prime[k];
        dfs(k+1,val*(ksm(prime[k],i+1)-ksm(prime[k],i))%mod*(i-1)%mod,x);
    }
}
ll get(ll x)
{
    x%=mod;
    return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;
}
ll getsum(ll x)
{
    if(x<N)return xphi[x];
    if(mp.find(x)!=mp.end())return mp[x];
    ll ret = get(x);
    for(ll i=2,j;i<=x;i=j+1)
    {
        j=x/(x/i);
        ret = (ret-(j-i+1)%mod*((i+j)%mod)%mod*inv2%mod*(getsum(x/i)%mod))%mod;
    }
    return mp[x]=ret;
}
int main()
{
    scanf("%lld",&n);
    init();
    tot1=0;
    while(1ll*prime[tot1+1]*prime[tot1+1]<=n)tot1++;
    dfs(1,1,1);
    ll ans = 0;
    for(int i=1;i<=cnt;i++)
        ans=(ans+1ll*h[i].second*getsum(n/h[i].first))%mod;
    ans=(ans+mod)%mod;
    cout << ans;
    return 0;
}
/*
10000000000
*/