题意 设d(n)为n的因子的个数，让你求 sumri=ld(ik)%998244353
题解 这题主要用到了一些定理和欧拉筛法。 首先我们应该思考对于d(n)怎么能简单计算出来。 这里有一个定理，由唯一分解定理知 n=pk11∗pk22∗... ，其中 pi 为素数，而 d(n)=(k1+1)∗(k2+1)∗... 。 这时我们就能简单的计算出d(n)，同理可以推出 d(nk)=(k∗k1+1)∗(k∗k2+1)∗... 。 现在对于我们的问题就是怎么快速的将区间[l,r]中的数唯一分解出来，如果直接l-r遍历分解的话会超时。那么怎么快速求呢？ 这里要知道d(n)是一个积性函数，而积性函数有一个性质就是f(a*b)=f(a)*f(b)，这里gcd(a,b)=1即a,b互质。而这里d(n)中对于每一个因子 pi 来说都是互质的，所以对于每个质数来说，其对答案的贡献都是互不影响的。所以我们对区间[l,r]直接对于每个质数计算贡献而不是用区间中数一个个去分解即可。 最后还有一个问题就是l和r的范围为 1012 ，那么这里按理说应该筛出 1012 以内的所有质数（比赛时我就是因为这个放弃的，不过我上面那个对质数算贡献也没想到，好菜QAQ），但是这样会超时。这里要知道一个知识，就是对于n以内的数， n√ -n中的数没有被1- n√ 中素数筛出来的数一定是素数。（可以用反证法证明）所以对于这题其实我们只需要筛出 106 以内所有素数即可。
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f typedef long long ll; const int maxn = 1e6+5; const int mod = 998244353; //num为10^6以内素数的个数，prime[]储存这些素数 ll l,r,k,prime[maxn],num,sz[maxn],res[maxn]; bool isprime[maxn]; void get_Prime() //欧拉筛法 { num = 0; memset(isprime,true,sizeof(isprime)); for(int i=2;i<maxn;i++) { if(isprime[i]) prime[num++] = i; for(int j=0;j<num&&prime[j]*i<maxn;j++) { isprime[i*prime[j]] = false; if(i%prime[j]==0) break; } } } int main() { int t; get_Prime(); scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&l,&r,&k); for(ll i=l;i<=r;i++) { sz[i-l] = i;//储存分解的数 res[i-l] = 1;//储存区间中数的d()值 } //对于每个素数对区间开始分解 for(int i=0;i<num&&prime[i]*prime[i]<=r;i++) { //从区间中该素数的最小倍数开始分解 for(ll j=prime[i]*(l/prime[i]);j<=r;j+=prime[i]) { if(j<l) continue; ll cnt=0; while(sz[j-l]%prime[i]==0) { cnt++; sz[j-l]/=prime[i]; } res[j-l] = (res[j-l]*(cnt*k+1))%mod; } } ll ans=0; for(ll i=l;i<=r;i++) { //如果分解剩下的数大于1那么就一定是一个大于10^6的素数 if(sz[i-l]>1) res[i-l] = (res[i-l]*(k+1))%mod; ans = (ans+res[i-l])%mod; } printf("%lld\n",ans); } return 0; }