2017多校4-3 Counting Divisors

数论

题意

给你l，r，k。对于每个l到r之间的数i，统计 ik 的因子个数。求和。

思路

设 n=pc11pc22...pcmm ，则 d(nk)=(kc1+1)(kc2+1)...(kcm+1) 。 枚举不超过 r√ 的所有质数 p ，再枚举区间[l,r]中所有 p 的倍数，将其分解质因数，最后剩下的部分就是超过r√的质数，只可能是 0 个或1个。 时间复杂度 O(r√+(r−l+1)loglog(r−l+1)) 。

比赛的时候是枚举l到r的每一个数，这样很慢。可以枚举素数，处理他在l到r之间的倍数们，这样复杂度就小了很多。

代码

#include<bits\stdc++.h> #define M(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long LL; const int MOD=998244353; const int MAXN=1e6+500; int prime[MAXN];vector<int> pri;int rec[MAXN]; int scc; LL num[MAXN]; LL ans[MAXN]; void init_prime_table() { scc=0; memset(prime, true, sizeof(prime)); prime[0]=prime[1]=false; for(int i=2; i<=MAXN;i++) { if(prime[i]) rec[scc++]=i; for(int j=0; j<scc && rec[j]<=MAXN/i; ++j) { prime[i * rec[j]]=false; if(i % rec[j]==0) break; } } } void solve(LL l,LL r,LL k) { for(int i=0;i<scc;i++) { LL now=(l+rec[i]-1)/rec[i]*rec[i]; while(now<=r) { LL cnt=0; while(num[now-l]%rec[i]==0) { cnt++; num[now-l]/=rec[i]; } ans[now-l]*=cnt*k+1; ans[now-l]%=MOD; now+=rec[i]; } } } int main() { init_prime_table(); int T;cin>>T; while(T--) { LL l, r, k;cin>>l>>r>>k; for(LL i=0;i<(r-l+1);i++) { num[i]=l+i; ans[i]=1; } solve(l, r, k); LL res=0; for(int i=0;i<(r-l+1);i++) { if(num[i]==1) res+=ans[i]; else res+=ans[i]*(k+1); res%=MOD; } printf("%lld\n", res); } return 0; }