比赛的时候把公式扣出来了，，但是没有想到用筛法算公因子，，默默学习一下。。
题解：设n=p1^（c1）p2^{c2}...pm^{cm},n=p1^c1*p2^c2...pm^cm，则d(n^k)=(k*c1+1)(k*c2+1)...(k*cm+1)d(nk)=(kc1+1)(kc2+1)...(kcm+1)。然后由于l,r的值很大，但是l-r的范围还是可以接受的，所以我们用一个偏移数组
来存l<=n<=r数的d(n)。然后就是求解l~r中质因子的过程了，这里用筛法求。首先我们知道，一个数可以唯一分解为若干个素数幂的乘积，那么我们先筛出sqrt(r)范围内的所有素数，那么(l,r）中所有的非素数都可以用sqrt(r）
中的素数表示（过程有点类似欧拉函数的筛法）。比赛的时候没想到用筛法，一直挂机，难受。，
ac代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
const int mod=;
ll prime[maxn];
int vis[maxn];
ll d[maxn],arr[maxn];
// 比较大的数组放全局
int ret;
void init()
{
memset(vis,,sizeof(vis));
ret=;
for(ll i=;i<maxn;i++)
{
if(!vis[i])
{
prime[++ret]=i;
for(ll j=i*;j<=maxn;j+=i) vis[j]=;
}
}
}
void solve(ll l,ll r,ll k)
{
for(ll i=;i<=ret;i++)
{
ll pos=(l+prime[i]-)/prime[i]*prime[i];// 定位
while(pos<=r)
{
int zz=;//
while(arr[pos-l]%prime[i]==)
{
zz++;
arr[pos-l]/=prime[i];
}
d[pos-l]*=(k*zz+);
d[pos-l]%=mod;
pos+=prime[i];
}
}
ll ans=;
for(ll i=l;i<=r;i++)
{
if(arr[i-l]==) ans=(ans+d[i-l])%mod;
else ans=(ans+d[i-l]*(k+))%mod;//唯一分解定理
}
printf("%lld\n",ans);
}
// 数差在一定范围 就可以用偏移数组
int main()
{
int t;
scanf("%d",&t);
init();
while(t--)
{
ll l,r,k;
scanf("%lld %lld %lld",&l,&r,&k);
for(ll i=l;i<=r;i++)
{
arr[i-l]=i;
d[i-l]=;
}
solve(l,r,k);
}
return ;
}
自己选的路，跪着也要走下去
埃氏筛法，这里也是一个算各个素数的贡献的思想，由于素数是有限的，所以可以可以把问题的规模变小 by-2017-09-17