LOJ6053 简单的函数

题目传送门
分析：
对于这道题来说，当\(x\)为质数时：

\(~~~~f(x)=x-1+2[x=2]\)

因为除2以外的质数都是奇数，它们与1异或就是减一，然后2就是加一

然后我们先来康康怎么快速求一个子问题：

\(~~~~F(n)=\sum_{i=1}^{n}f(i)[i\in Prime]\)

然后就要学学一个叫min25筛的奇妙的东西
对于一个函数f(x)：
1、\(f(x)\)可以用多项式表达。。。（一般都可以吧2333）
2、\(f(x^k)\)可以快速算出（这里的快速是指可以预处理之类的可以很快求出的东西，因为min25筛的复杂度会乘上求\(f(x^k)\)时的复杂度，所以这里的快速算出自己算复杂度拿捏一下就好了）

首先先引入一个函数\(G_{k}(n,m)\)

\(G_{k}(n,m)=\sum_{i=1}^{n}i^k[i\in Prime~||~minP_{i}>P_{m}]\)

其中\(minP_{i}\)代表 \(i\) 的最小质因子，\(P_{m}\)代表第\(m\)个质数
那么在当\(n>1\)时我们的子问题就可以转化：

\(~~~~\sum_{i=1}^{n}f(i)[i\in Prime]\)

\(=\sum_{i=1}^{n}(i-1)[i\in Prime]+2\)

\(=\sum_{i=1}^{n}i^1[i\in Prime]-\sum_{i=1}^{n}i^0[i\in Prime]+2\)

\(=G_{1}(n,|P|)-G_{0}(n,|P|)+2\)

其中\(|P|\)为\(n\)以内的质数个数

奥妙重重

于是乎我们开始思考如何推导\(G_{k}\)
考虑从\(G_{k}(n,m-1)\)推出\(G_{k}(n,m)\)相当于去除最小质因子为\(P_{m}\)的 \(i\) 的\(f(i)\)
容斥一发：

\(~~~G_{k}(n,m)=G_{k}(n,m-1)-P_{m}^k(G_{k}(\lfloor\frac{n}{P_m}\rfloor,m-1)+G_k(P_m-1,m-1))\)

然后\(G_k(n,0)=\sum_{i=1}^{n}i^k\)，当\(k\)较小的时候是可以快速求的
递推过程中我们只需要考虑\(\sqrt n\)种取值
然后从前往后枚举质因数较大的取值不会影响小的取值，所以反向更新
复杂度\(O(N/ln\sqrt N)\)
很卡，所以考虑优化
当\(P_m^2>n\)时，\(G_k(n,m)=G_k(n,m-1)\)
剪枝之后的复杂度是\(O(N^\frac{3}{4})\)（不会证dbq），实际上好像会快很多2333

然后我们知道了\(F(n)\)
尝试求一下前缀和\(S(n,m)\)

\(~~~~S(n,m)=\sum_{i=1}^{n}F(i)[minP_i\ge P_m]\)

\(=F(n)-F(P_m-1)+\sum_{i=m}^{|P|}\sum_{j=1}^{P_i^{j-1}~\le N}(f(P_i^j)\cdot S(\lfloor\frac{N}{P_i^j}\rfloor,i+1)+f(P_i^{j+1}))\)

由于\(P_m\le \sqrt N\)，这些值的\(F\)值之前筛的时候都是算出来了的（奥妙重重）
那么答案其实就是\(S(N,1)+f(1)\)
\(F(n)\)预处理一下
然后\(S(n,1)\)直接记忆化搜索
OrzOrz

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
#include<string>

#define maxn 500005
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define inv2 500000004

using namespace std;

inline long long getint()
{
    long long num=0,flag=1;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
    return num*flag;
}

long long N,S;
long long pri[maxn],np[maxn],cnt,sumpri[maxn];
long long G0[maxn],G1[maxn];
long long num[maxn],tot;
long long pos1[maxn],pos2[maxn];

inline void init()
{
    for(int i=2;i<maxn;i++)
    {
        if(!np[i])pri[++cnt]=i,sumpri[cnt]=(sumpri[cnt-1]+i)%MOD;
        for(int j=1;j<=cnt&&i*pri[j]<maxn;j++)
        {
            np[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}

inline long long getsum(long long n,long long m)
{
    if(n<2||pri[m]>n)return 0;
    long long k=(n<=S)?pos1[n]:pos2[N/n],ret=(G1[k]-sumpri[m-1]-G0[k]+m-1)%MOD;
    ret+=(m==1)<<1;
    for(int i=m;i<=cnt&&pri[i]*pri[i]<=n;i++)
    {
        long long tmp=pri[i];
        for(int j=1;tmp*pri[i]<=n;j++,tmp*=pri[i])
            ret=(ret+(getsum(n/tmp,i+1)*(pri[i]^j)%MOD)+(pri[i]^(j+1))%MOD)%MOD;
    }
    return ret;
}

int main()
{
    init();
    N=getint();
    S=sqrt(N);
    for(long long i=1,j;i<=N;i=j+1)
    {
        j=N/(N/i);num[++tot]=N/i;
        G0[tot]=(num[tot]-1)%MOD;
        G1[tot]=(num[tot]%MOD)*((num[tot]+1)%MOD)%MOD*inv2%MOD;
        G1[tot]--;
        if(num[tot]<=S)pos1[num[tot]]=tot;
        else pos2[j]=tot;
    }
    for(int j=1;j<=cnt;j++)
        for(int i=1;i<=tot&&pri[j]*pri[j]<=num[i];i++)
        {
            int k=(num[i]/pri[j]<=S)?pos1[num[i]/pri[j]]:pos2[N/(num[i]/pri[j])];
            (G0[i]+=MOD-(G0[k]-(j-1))%MOD)%=MOD;
            (G1[i]+=MOD-pri[j]*(G1[k]-sumpri[j-1])%MOD)%=MOD;
        }
    printf("%lld\n",(getsum(N,1)+1+MOD)%MOD);
}

LOJ6053 简单的函数

原文：https://www.cnblogs.com/Darknesses/p/12191855.html