- Counting Divisors
In mathematics, the function d(n) d(n) denotes the number of divisors of positive integer n n. For example, d(12)=6 d(12)=6 because 1,2,3,4,6,12 1,2,3,4,6,12 are all 12 12's divisors. In this problem, given l,r l,r and k k, your task is to calculate the following thing :
(∑i=lrd(ik))mod998244353 (∑i=lrd(ik))mod998244353 Input The first line of the input contains an integer T(1≤T≤15) T(1≤T≤15) , denoting the number of test cases. In each test case, there are 3 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107) 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 题意应该很好理解了，就是求上图那个式子的累加和，而上面那个式子就是求每个数的因子个数。 对于 l，r 两个数都很大，所以暴力是不可能的。 对于每个数 的因子，我们先列几个找一下规律。 1.对于每个素数，所有的因子都是2个。 2.非素数的情况： 比如： d(2)=2; d(4)=3; d(6)= 4; d(12)=6; d(3)=2; d(9)=3; d(18)=6; d(4)=3; d(8)=4; d(16)=5; 由唯一分解定理，对于每个整数都可以分为素数次方的乘积。 即对于4=2^2; d(4)=d(2)*2-1; 16=2^4; d(16)=d(2)*4-1; 那么d( i^k )=d( i )*k-1; 那么对于 几个素数相乘的规律 有： 比如 d( 12 )=d( 2^2^3 )= d(4)*d(3)=2*d(2)*d(3); 即对于这种情况其实就是等于每个素数的乘积，满足一个积性函数的性质吧，（d(x*y)=d(x)*d(y) ) 虽然我也不知道为啥。 那么现在就是实现了。 对于每个数我们需要拆分为素因子的乘积，用一个数组存着每个数对于答案的贡献值，最后需要判断一下每个数除完后是否有剩余，如果还有就需要加一下。 直接用唯一分解定理的模板是不行的会超时。 个人觉得跟 light OJ 1197 Help Hanzo 这个题思路差不多。 代码： #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #define maxn 1000100 using namespace std; typedef long long ll; ll l,r,k; bool vis[maxn]; int prime[maxn]; ll a[maxn],b[maxn]; int len; const ll MOD=998244353; void init() { len=0; for(int i=2; i<maxn; i++) { if(!vis[i]) prime[len++]=i; for(int j=0; j<len&&i*prime[j]<maxn; j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } } int main() { int T; scanf("%d",&T); init(); while(T--) { ll ans=0; scanf("%lld%lld%lld",&l,&r,&k); for(ll i=0;i<r-l+1;i++) { a[i]=i+l; //记录每个数字的最后状态 b[i]=1; //存每个数字的贡献值 } for(ll i=0;i<len&&prime[i]<=r;i++) { ll tem,t; ll cnt=(l-1+prime[i])/prime[i]*prime[i]; while(cnt<=r) { t=cnt; tem=0; while(t%prime[i]==0) { tem++; t/=prime[i]; a[cnt-l]/=prime[i]; } b[cnt-l]=((b[cnt-l]%MOD)*((k*tem+1)%MOD))%MOD; cnt+=prime[i]; } } for(ll i=0;i<r-l+1;i++) { if(a[i]==1) ans=(ans+b[i])%MOD; else ans=(ans+((b[i]%MOD)*((k+1)%MOD)))%MOD; } printf("%lld\n",ans); } }