2019徐州网络赛H ：function （min25筛）

题意：f(i)=i的幂次之和。 求(N+1-i)*f(i)之和。

思路：可以推论得对于一个素数p^k，其贡献是ans=(N+1)[N/(P^k)]+P^k(1+2+3...N/(P^k));

我们分两部分统计答案即可，在p<=sqrt(N)时，可以暴力（阶乘那样一直除）统计答案。 p>sqrt(N)时，我们可以利用min25的消息得到。

因为p>sqrt(N)，这个时候k=1，所以贡献为(N+1)*(N/p)+p*(1+2+...N/p)；我们把N/p相同的拉出来即可，而这个东西正好就是min25的基本操作。

N/p有根号级别个，我们把素数个数前缀和保存到h[]里，素数和的前缀和保存到g[]里，就不难得到区间素数个数，以及区间素数和。

wa点：写出来容易爆炸long long。

前缀和公式：x*(x+1)/2；由于x*(x+1)可能爆炸ll，所以我们得到x=x%Mod再进行计算，这个时候就不能/2了，需要*2的逆元。

ans：ans没必要每次维护到[0,Mod)这个范围内，我们最后一次性处理就好了，毕竟每次加减的都是[0,Mod)这个范围的数，最后结果一定再long long范围内。这样会

快一些。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int Mod=,inv2=(Mod+)/;

int qpow(int a,int x){

    int res=; while(x){

        if(x&) res=1LL*res*a%Mod; x>>=;

        a=1LL*a*a%Mod;

    } return res;

}

struct min25 //很多部分需要long，不要搞错了

{

    ll p[maxn],sp1[maxn],N;

    ll g1[maxn],h[maxn];int Sqr,ind1[maxn],ind2[maxn],num,tot;

    ll w[maxn]; bool vis[maxn];

    int MOD(int x){ if(x>=Mod) x-=Mod;return x; }

    void prime() //得到素数，sp1，sp2

    {

        rep(i,,Sqr){

            if(!vis[i]){

                p[++num]=i;

                sp1[num]=MOD(sp1[num-]+i);

            }

            for(int j=;j<=num&&p[j]*i<=Sqr;j++){

                vis[p[j]*i]=;

                if(i%p[j]==) break;

            }

        }

    }

    void getind()

    {

        for(ll i=;i<=N;i++){

            ll now=N/i,j=N/now,t=now%Mod;

            w[++tot]=now;

            g1[tot]=MOD(t*(t+)/%Mod+Mod-); //因为我们全部都不考虑1。

            h[tot]=t-;

            if(g1[tot]<) g1[tot]+=Mod;

            if(h[tot]<) h[tot]+=Mod;

            if(now<=Sqr) ind1[now]=tot;

            else ind2[j]=tot;

            i=j;

        }

    }

    void getg()

    {

        rep(i,,num){ //注意w里面的东西是递减的,所以可以滚动

            for(int j=;j<=tot&&p[i]<=w[j]/p[i];j++){

                ll now=w[j]/p[i];

                int k=now<=Sqr?ind1[now]:ind2[N/now];

                g1[j]=MOD(g1[j]-1LL*p[i]*(g1[k]-sp1[i-]+Mod)%Mod+Mod);

                h[j]=(h[j]-(h[k]-i++Mod)%Mod+Mod)%Mod;

            }

        }

    }

    ll get(ll x) { return x*(x+)%Mod*inv2%Mod; }//x需要实现%Mod，不然爆ll，所以也不能用/2，而用逆元。

    void solve(ll n)

    {

        N=n; Sqr=sqrt(N);

        prime(); //筛根号部分素数。

        ll ans=;

        rep(i,,num){

            for(ll e=p[i];e<=N;e*=p[i]){

                ans+=(N+)%Mod*(N/e)%Mod-e%Mod*get(N/e%Mod)%Mod;

            }

        }

        getind();

        getg();

        rep(i,,Sqr-){

            ans+=(N+)%Mod*i*((h[i]-h[i+]+Mod)%Mod)%Mod; //多少个素数满足N/p=i

            ans-=1LL*get(i)*((g1[i]-g1[i+]+Mod)%Mod)%Mod; //素数之和

        }

        ans%=Mod; if(ans<) ans+=Mod;

        printf("%lld\n",ans%Mod);

    }

}T;

int main()

{

    ll N;

    scanf("%lld",&N);

    T.solve(N);

    return ;

}

，很多地方容易爆long long。

2019徐州网络赛H ：function （min25筛）的相关教程结束。