题解 P3362 【Cool loves shaxian】

· · 题解

本题数据范围:n<=1e7 d<=1e18 q<=5e4

算法一

先 O(n log d) 预处理出1~n的d次方。

然后先枚举一个i，再枚举一个i的倍数j，f(i*j)就加上i的d次方。

在做一个前缀和就行了。

时间复杂度: O(n log d+n log n+q) 预计得分:45

//by zykykyk
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#define rg register
#define il inline
#define vd void
#define ll long long
#define mod 1000000007
#define maxn 5000010
#define For(i,x,y) for (rg int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (rg int i=(x);i>=(y);i--)
#define cross(i,k) for (rg int i=first[k];i;i=last[i])
using namespace std;
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll read(){
    ll x=0;int ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,q,p[maxn],sum[maxn];
ll d;
il int power(int x,ll y){
    int ans=1;
    for (;y;y>>=1,x=1ll*x*x%mod) if (y&1) ans=1ll*ans*x%mod;
    return ans;
}
il vd init(){
    n=read(),d=read(),q=read();
    For(i,1,n) p[i]=power(i,d);
    For(i,1,n)
        For(j,1,n/i) (sum[j*i]+=p[i])%=mod;
    For(i,1,maxn-1) (sum[i]+=sum[i-1])%=mod;
}

int l,r;
il vd work(){
    while (q--){
        l=read(),r=read();
        printf("%d\n",((sum[r]-sum[l-1])%mod+mod)%mod);
    }
}

int main(){
    init(),work();
}

算法二

我们发现主要复杂度在预处理1~n的d次方。

考虑怎么优化。

我们设q(i)为i^d，不难发现q(i)是个完全积性函数。

因此我们可以直接欧拉筛 O(n) 预处理。

接下来同算法一。

时间复杂度: O(n+n log n+q) 预计得分:60

这样就可以看AC代码了

//by zykykyk
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#define rg register
#define il inline
#define vd void
#define ll long long
#define mod 1000000007
#define maxn 5000010
#define For(i,x,y) for (rg int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (rg int i=(x);i>=(y);i--)
#define cross(i,k) for (rg int i=first[k];i;i=last[i])
using namespace std;
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll read(){
    ll x=0;int ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot,q,vis[maxn],P[maxn],p[maxn],sum[maxn];
ll d;
il int power(int x,ll y){
    int ans=1;
    for (;y;y>>=1,x=1ll*x*x%mod) if (y&1) ans=1ll*ans*x%mod;
    return ans;
}
il vd init(){
    n=read(),d=read(),q=read();
    For(i,2,n){
        if (!vis[i]) p[i]=power(i,d),P[++tot]=i;
        for (int j=1;i*P[j]<=n&&j<=tot;j++){
            vis[i*P[j]]=P[j];
            if (i%P[j]==0) break;
        }
    }
    int l=sqrt(n);
    For(i,1,l) p[i]=power(i,d);
    For(i,l+1,n) 
        if (vis[i]) p[i]=1ll*p[vis[i]]*p[i/vis[i]]%mod;
    For(i,1,n)
        For(j,1,n/i) (sum[j*i]+=p[i])%=mod;
    For(i,1,n) (sum[i]+=sum[i-1])%=mod;

}

int l,r;
il vd work(){
    while (q--){
        l=read(),r=read();
        printf("%d\n",((sum[r]-sum[l-1])%mod+mod)%mod);
    }
}

int main(){
    init(),work();
}

算法三

再仔细看可以发现f(i)是个积性函数，那么我们就可以欧拉筛 O(n) 预处理出f(i)，然后做个前缀和就行了。

1.i为素数，$f(i)=i^d

2.i%p[j]!=0 f(i*p_j)=f(i)*f(p_j)

3.i%p[j]==0 这个比较复杂，以下是f老板说的：我们要考虑的是i*p_j比i多的约数是什么，假设i*pj是pj的k次，那多出来的约数都是pj^k再乘个数，否则已经被i包含了，那只要考虑这些数的贡献就行，也就是f(i*p_j/p_j^k)*(p_j^k)^d

时间复杂度: O(n+q) 预计得分:100

//by zykykyk
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#define rg register
#define il inline
#define vd void
#define ll long long
#define mod 1000000007
#define maxn 10000010
#define For(i,x,y) for (rg int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (rg int i=(x);i>=(y);i--)
#define cross(i,k) for (rg int i=first[k];i;i=last[i])
using namespace std;
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll read(){
    ll x=0;int ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot,q,x,P[maxn],minp[maxn],minpd[maxn],sum[maxn];
bool vis[maxn];
ll d;
il int power(int x,ll y){
    int ans=1;
    for (;y;y>>=1,x=1ll*x*x%mod) if (y&1) ans=1ll*ans*x%mod;
    return ans;
}
il vd init(){
    n=read(),d=read(),q=read();
    sum[1]=1;
    For(i,2,n){
        if (!vis[i]) P[++tot]=minp[i]=i,minpd[i]=sum[i]=power(i,d),sum[i]=(sum[i]+1)%mod;
        for (int j=1;i*P[j]<=n&&j<=tot;j++){
            int k=i*P[j];
            vis[k]=1;
            if (i%P[j]==0){
                minp[k]=minp[i]*P[j];
                minpd[k]=1ll*minpd[i]*minpd[P[j]]%mod;
                sum[k]=(sum[i]+1ll*minpd[k]*sum[k/minp[k]]%mod)%mod;
                break;
            }
            else {
                minp[k]=P[j];
                minpd[k]=minpd[P[j]];
                sum[k]=1ll*sum[i]*sum[P[j]]%mod;
            }
        }
    }
    For(i,2,n) (sum[i]+=sum[i-1])%=mod;
}

int l,r;
il vd work(){
    while (q--){
        l=read(),r=read();
        printf("%d\n",((sum[r]-sum[l-1])%mod+mod)%mod);
    }
}

int main(){
    init(),work();
}

原来此题128MB，丧心病狂