http://acm.hdu.edu.cn/showproblem.php?pid=6069
求一段区间里面所有数的因子个数和,很直白的去暴力必定超时,
因为任何数都可以被分解为若干个质数相乘的形式,那么意味着可以将所有的质数找到,然后去不断的给一个范围里的数去这个质数来筛.
以后碰到计算因子个数的题目,感觉可以借鉴这道题的方法.
#include<bits/stdc++.h> using namespace std; const long long int MOD=998244353; long long int pr[1111111]; bool vis[1111111]; long long int num[1111111]; long long int sum[1111111]; long long int _js=0; void _loading(){ _js=0; memset(vis,true,sizeof(vis)); vis[0]=0; vis[1]=0; for(int i=0;i<=1000005;i++) { if(vis[i]==0)continue; vis[i]=0; pr[_js++]=i; for(int j=i*2;j<=1000005;j=j+i) vis[j]=0; } } int main(){ long long int l,r,k; long long int t; _loading(); scanf("%lld",&t); while(t--) { scanf("%lld%lld%lld",&l,&r,&k); long long int i,j; for(i=0;i<=r-l;i++) { num[i]=i+l; sum[i]=1; } for(i=0;i<_js;i++) { long long int i1=(l/pr[i]+(l%pr[i]? 1:0 ))*pr[i]; for(j=i1;j<=r;j=j+pr[i]) { long long int _js1=0; while(num[j-l]%pr[i]==0) { _js1++; num[j-l]/=pr[i]; } sum[j-l]=sum[j-l]*(1LL*_js1*k+1)%MOD; } } long long int ans=0; for(i=0;i<=r-l;i++) { if(num[i]!=1)sum[i]=sum[i]*(k+1)%MOD; ans=(ans+sum[i])%MOD; } cout<<ans<<endl; } return 0; }
