Counting Divisors

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 2762    Accepted Submission(s): 1021 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 Source 2017 Multi-University Training Contest - Team 4 题意：d为因子个数，求(∑i=lrd(ik))mod998244353

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

#include <iostream> #include<cstdio> #include<math.h> #define mod 998244353 #define ll long long using namespace std; const int N=1e6+5; int pri[N],cnt; ll sum[N]; ll pp[N]; bool number[N+1]; void getprime() { cnt = 0; for (int i = 2; i <= N; i++)//快速筛选 { if (!number[i]) pri[++cnt] = i; // means primer. for (int j = 1; j <= cnt && pri[j] * i <= N; j++) { number[i*pri[j]] = 1; if (i % pri[j] == 0)break; } } } int main() { getprime(); //cout<<cnt<<endl; ll n,i,k,l,r; int t; scanf("%d",&t); while(t--){ scanf("%lld%lld%lld",&l,&r,&k); for(ll i=0;i<N;i++) {sum[i]=1;pp[i]=1;} ll res=0; ll i; ll tt=sqrt(r); for(i=1;pri[i]<=tt;i++) { ll a,b; if(l%pri[i]==0) a=l/pri[i]; else a=l/pri[i]+1; b=r/pri[i]; for(ll j=a;j<=b;j++) { if(j*pri[i]-l<0) continue; ll num=1; ll s=j; ll temp=pri[i]; while(s%pri[i]==0) { num++; s/=pri[i]; temp*=pri[i]; } pp[j*pri[i]-l]*=temp; sum[j*pri[i]-l]*=(1+k*num)%mod; sum[j*pri[i]-l]%=mod; } if(i==cnt) break; } for(ll i=l;i<=r;i++) if(pp[i-l]!=i) { sum[i-l]*=1+k; sum[i-l]%=mod; } for(ll i=l;i<=r;i++) { res+=sum[i-l]; res%=mod; // cout<<i<<endl; } cout<<res<<endl; } return 0; }