正题

题目链接:https://loj.ac/p/6053

题目大意

定义一个积性函数\(f(p^c)=p\ xor\ c\)，求\(\sum_{i=1}^nf(i)\)

解题思路

异或这个东西不太好搞，要考虑怎么求出\(g\)数组。

当\(p\)为质数时\(f(p)=p-1\)，所以我们让\(g(n)=\sum_{i=1}^n[i\in Pri](i-1)\)就好了。

然后因为\(i-1\)不是完全积性函数，所以拆成\(i\)和\(1\)分开来就好了。

然后因为\(f(2)=3\)，所以答案会少\(2\)，加回去就好了。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const ll N=1e6+10,P=1e9+7;

ll n,T,cnt,tot,w[N],pri[N],sp[N],g1[N],g2[N],ind1[N],ind2[N];

bool v[N];

void init(ll n){

    for(ll i=2;i<=n;i++){

        if(!v[i]){

            pri[++cnt]=i;

            sp[cnt]=sp[cnt-1]+i;

        }

        for(ll j=1;j<=cnt&&i*pri[j]<=n;j++){

            v[i*pri[j]]=1;

            if(i%pri[j]==0)break;

        }

    }

    return;

}

ll S(ll x,ll y){

    if(pri[y]>=x)return 0;

    ll pos=(x>T)?ind2[n/x]:ind1[x];

    ll ans=((g2[pos]-g1[pos])-(sp[y]-y)+P)%P;

    if(y==0)ans+=2;

    for(ll k=y+1;k<=cnt&&pri[k]*pri[k]<=x;k++)

        for(ll e=1,p=pri[k];p<=x;p=p*pri[k],e++)

            (ans+=(pri[k]^e)*(S(x/p,k)+(e!=1))%P)%=P;

    return ans;

}

signed main()

{

    scanf("%lld",&n);

    if(n==1)return puts("1")&0;

    T=sqrt(n);init(T);

    for(ll l=1,r;l<=n;l=r+1){

        ll x=n/l;r=n/(n/l);

        w[++tot]=x;x%=P;

        g1[tot]=x-1;

        g2[tot]=x*(x+1)/2%P-1;

        if(n/l<=T)ind1[n/l]=tot;

        else ind2[n/(n/l)]=tot;

    }

    for(ll i=1;i<=cnt;i++)

        for(ll j=1;j<=tot&&pri[i]*pri[i]<=w[j];j++){

            ll k=w[j]/pri[i];k=(k>T)?ind2[n/k]:ind1[k];

            (g2[j]+=P-(g2[k]-sp[i-1])*pri[i]%P)%=P;

            (g1[j]+=P-(g1[k]-i+1)%P)%=P;

        }

    printf("%lld\n",S(n,0)+1);

    return 0;

}

巴特西

Loj#6053-简单的函数【Min25筛】

正题

题目大意

解题思路

code

最新文章

热门文章