比赛的时候把公式扣出来了，，但是没有想到用筛法算公因子，，默默学习一下。。
题解：设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+5; const int mod=998244353; ll prime[maxn]; int vis[maxn]; ll d[maxn],arr[maxn]; // 比较大的数组放全局 int ret; void init() { memset(vis,0,sizeof(vis)); ret=0; for(ll i=2;i<maxn;i++) { if(!vis[i]) { prime[++ret]=i; for(ll j=i*2;j<=maxn;j+=i) vis[j]=1; } } } void solve(ll l,ll r,ll k) { for(ll i=1;i<=ret;i++) { ll pos=(l+prime[i]-1)/prime[i]*prime[i];// 定位 while(pos<=r) { int zz=0;// while(arr[pos-l]%prime[i]==0) { zz++; arr[pos-l]/=prime[i]; } d[pos-l]*=(k*zz+1); d[pos-l]%=mod; pos+=prime[i]; } } ll ans=0; for(ll i=l;i<=r;i++) { if(arr[i-l]==1) ans=(ans+d[i-l])%mod; else ans=(ans+d[i-l]*(k+1))%mod;//唯一分解定理 } printf("%lld ",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]=1; } solve(l,r,k); } return 0; }
自己选的路，跪着也要走下去
埃氏筛法，这里也是一个算各个素数的贡献的思想，由于素数是有限的，所以可以可以把问题的规模变小 by-2017-09-17