http://acm.hdu.edu.cn/showproblem.php?pid=6069
【题意】
给定l,r,k，求
d(n)是n的因子个数
【思路】
【Accepted】
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<map> 10 #include<vector> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 const int maxn=1e6+3; 15 const ll mod=998244353; 16 ll l,r,k; 17 bool isprime[maxn]; 18 int prime[maxn]; 19 int cnt; 20 ll tot[maxn]; 21 vector<int> s[maxn]; 22 ll a[maxn]; 23 void init() 24 { 25 memset(isprime,true,sizeof(isprime)); 26 isprime[1]=false; 27 for(int i=2;i<maxn;i++) 28 { 29 if(isprime[i]) 30 { 31 for(int k=2*i;k<maxn;k+=i) 32 { 33 isprime[k]=false; 34 } 35 } 36 } 37 cnt=0; 38 for(int i=1;i<maxn;i++) 39 { 40 if(isprime[i]) 41 { 42 prime[cnt++]=i; 43 } 44 } 45 } 46 ll fac(ll& num,ll p) 47 { 48 ll cou=0; 49 while(num%p==0) 50 { 51 cou++; 52 num/=p; 53 } 54 return cou; 55 } 56 57 int main() 58 { 59 init(); 60 int T; 61 scanf("%d",&T); 62 while(T--) 63 { 64 scanf("%lld%lld%lld",&l,&r,&k); 65 for(int i=0;i<=r-l;i++) 66 { 67 a[i]=(ll)i+l; 68 tot[i]=1; 69 } 70 for(int i=0;i<cnt;i++) 71 { 72 if(prime[i]>r) break; 73 ll cou=l/(ll)prime[i]; 74 if(l%(ll)prime[i]) cou++; 75 for(ll j=cou*(ll)prime[i];j<=r;j+=(ll)prime[i]) 76 { 77 int num=(int)(j-l); 78 if(a[num]==1) continue; 79 ll sum=fac(a[num],prime[i]); 80 tot[num]=tot[num]*((k*sum)%mod+1)%mod; 81 } 82 } 83 ll ans; 84 if(l==1) ans=1; 85 else ans=0; 86 for(int i=0;i<=(int)(r-l);i++) 87 { 88 if(a[i]!=1) tot[i]=tot[i]*(k+1)%mod; 89 if(tot[i]!=1) 90 ans=(ans+tot[i])%mod; 91 } 92 cout<<ans<<endl; 93 } 94 return 0; 95 }