原题链接： HDU-6069
Counting Divisors
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2400 Accepted Submission(s): 870
Problem Description
In mathematics, the function d(n) denotes the number of divisors of positive integer n.
For example, d(12)=6 because 1,2,3,4,6,12 are all 12 ’s divisors.
In this problem, given l,r and k, your task is to calculate the following thing :
(∑i=lrd(ik))mod998244353
Input
The first line of the input contains an integer T(1≤T≤15) , denoting the number of test cases.
In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).
Output For each test case, print a single line containing an integer, denoting the answer.
Sample Input 3 1 5 1 1 10 2 1 100 3
Sample Output 10 48 2302
思路： 这道题一直 T ，赛后看题解也算是有所收获，在分解质因数的地方学会了一点优化。
具体思路： 生成素数筛，简单地利用质因数的计算方法即可，关键在于分解质因数的时候做一点优化。 算质数的倍数来分解质因数。 见代码。
PS.预处理的时候不要舍本逐末,瞎搞反而增加时间….
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define mem(s,t) memset(s,t,sizeof(s)) #define D(v) cout<<#v<<" "<<v<<endl #define inf 0x3f3f3f3f //#define LOCAL const ll MAXM =80000;//1e6范围内质数数量 const ll mod=998244353; const ll MAXN = 1e6+10; ll l,r,k,num[MAXN],cnt[MAXN]; bool isprime[MAXN]; ll tot =0; ll prime[MAXM]; void getprime() { mem(isprime,true); isprime[1]=false; tot=0; for(ll i=2; i<MAXN; i++) { if(isprime[i]) prime[++tot]=i; for(ll j=1;j<=tot && i*prime[j]<MAXN;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0)break; } } } int main() { getprime(); int t; scanf("%d",&t); while(t--){ scanf("%lld%lld%lld",&l,&r,&k); ll n=r-l; for(ll i=0;i<=n;i++){ num[i]=l+i; cnt[i]=1; } for(ll i=1;i<=tot;i++){ if(prime[i]*prime[i]>r) break; for(ll j=l/prime[i]*prime[i];j<=r;j+=prime[i]) if(j>=l){ ll o=0; while(num[j-l]%prime[i]==0){ o++; num[j-l]/=prime[i]; } cnt[j-l]=cnt[j-l]*(o*k%mod+1)%mod; } } ll ans=0; for(ll i=0;i<=n;i++){ if(num[i]>1) cnt[i]=cnt[i]*(k+1)%mod; //D(cnt[i]); ans=(ans+cnt[i])%mod; } printf("%lld\n",ans); } return 0; }附 标程：
#include<cstdio> typedef long long ll; const int N=1000010,P=998244353; int Case,i,j,k,p[N/10],tot,g[N],ans;ll n,l,r,f[N];bool v[N]; inline void work(ll p){ for(ll i=l/p*p;i<=r;i+=p)if(i>=l){ int o=0; while(f[i-l]%p==0)f[i-l]/=p,o++; g[i-l]=1LL*g[i-l]*(o*k+1)%P; } } int main(){ for(i=2;i<N;i++){ if(!v[i])p[tot++]=i; for(j=0;j<tot&&i*p[j]<N;j++){ v[i*p[j]]=1; if(i%p[j]==0)break; } } scanf("%d",&Case); while(Case--){ scanf("%lld%lld%d",&l,&r,&k); n=r-l; for(i=0;i<=n;i++)f[i]=i+l,g[i]=1; for(i=0;i<tot;i++){ if(1LL*p[i]*p[i]>r)break; work(p[i]); } for(ans=i=0;i<=n;i++){ if(f[i]>1)g[i]=1LL*g[i]*(k+1)%P; ans=(ans+g[i])%P; } printf("%d\n",ans); } return 0; }