loj124 除数函数求和 1

$\sum_{i=1}^n(\sum_{d|i}d^k)=\sum_{i=1}^n(i^k*{\lfloor}{\frac{n}{i}}{\rfloor})$

不能直接数论分块了，但是一看数据范围，可以线性筛啊

怎么筛呢？可以把所有的$i^k$筛出来。就是质数直接算，其他的根据$(a*b)^k=a^k*b^k$在被筛掉的时候递推出来。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 #define N 10000010

 #define md 1000000007

 bool nprime[N+];int prime[N+],len;

 ll A[N+],ans,n,k;

 ll poww(ll a,ll b)

 {

     ll base=a,ans=;

     while(b)

     {

         if(b&) ans=ans*base%md;

         base=base*base%md;

         b>>=;

     }

     return ans;

 }

 int main()

 {

     ll i,j;

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

     A[]=;

     for(i=;i<=n;i++)

     {

         if(!nprime[i])    prime[++len]=i,A[i]=poww(i,k);

         for(j=;j<=len&&i*prime[j]<=n;j++)

         {

             nprime[i*prime[j]]=;

             A[i*prime[j]]=A[i]*A[prime[j]]%md;

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

         }

     }

     for(i=;i<=n;i++)    ans=(ans+A[i]*(n/i)%md)%md;

     printf("%lld",ans);

     return ;

 }

巴特西

loj124 除数函数求和 1

最新文章

热门文章