自动搬运

查看原文

来自洛谷，原作者为

	夏色祭 **

搬运于2025-08-24 21:48:08，当前版本为作者最后更新于2018-04-12 22:33:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题数据范围: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)$，然后做个前缀和就行了。

$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，丧心病狂