hdu5608杜教筛

题意:给定函数\(f(x)\),有\(n^2-3*n+2=\sum_{d|n}f(d)\),求\(\sum_{i=1}^nf(i)\)

题解:很显然的杜教筛,假设\(g(n)=n^2-3*n+2\),那么有\(g=f*I\),由莫比乌斯反演,\(f=g*\mu\),可以O(nlogn)预处理到1e6,剩余部分杜教筛

我们先观察杜教筛的推导过程,假设要求\(s(n)=\sum_{i=1}^nf(i)\),

\(\sum_{i=1}^ng*f=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}f(i)=\sum_{d=1}^ng(d)S(\lfloor \frac{n}{d} \rfloor)\)

\(S(n)=\sum_{i=1}^ng*f-\sum_{i=1}^ng(d)S(\lfloor \frac{n}{d} \rfloor)\)

我们考虑s就是我们要求的答案,g是常函数,那么I*f就是g,所以前半部分即\(\sum_{i=1}^ng(i)\)

分块处理后半部分,复杂度\(O(n^{\frac{2}{3})\)

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

//#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

template<typename T>

inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>

inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=1000000+10,maxn=3000000+10,inf=0x3f3f3f3f;

int prime[N],cnt,mu[N];

bool mark[N];

ll f[N];

map<ll,ll>ff;

map<ll,ll>::iterator it1;

ll inv3=qp(3,mod-2);

void init()

{

    mu[1]=1;

    for(int i=2;i<N;i++)

    {

        if(!mark[i])prime[++cnt]=i,mu[i]=-1;

        for(int j=1;j<=cnt&&i*prime[j]<N;j++)

        {

            mark[i*prime[j]]=1;

            if(i%prime[j]==0)

            {

                mu[i*prime[j]]=0;

                break;

            }

            mu[i*prime[j]]=-mu[i];

        }

    }

    for(int i=1;i<N;i++)

        for(int j=i;j<N;j+=i)

        {

            ll te=1ll*(j/i-2)*(j/i-1)*mu[i];

            te=(te%mod+mod)%mod;

            add(f[j],te);

        }

//    printf("%lld\n",f[1000000]);

    for(int i=1;i<N;i++)add(f[i],f[i-1]);

}

ll getf(ll n)

{

    if(n<N)return f[n];

    if((it1=ff.find(n))!=ff.end())return it1->se;

    ll ans=n*(n+1)%mod*(n-4)%mod*inv3%mod+2ll*n%mod;

    ans=(ans%mod+mod)%mod;

    for(ll i=2,j;i<=n;i=j+1)

    {

        j=n/(n/i);

        sub(ans,1ll*(j-i+1)*getf(n/i)%mod);

    }

    return ff[n]=ans;

}

int main()

{

    init();

    int T;scanf("%d",&T);

    while(T--)

    {

        ll n;scanf("%lld",&n);

        printf("%lld\n",getf(n));

    }

    return 0;

}

/********************

********************/

巴特西

hdu5608杜教筛

最新文章

热门文章