Counting Divisors

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 2340    Accepted Submission(s): 841 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  

题目大意：

求给定的函数值，其中 d (i )：i 的因子个数

解题思路：

设有 n=pa11∗pa22∗...∗pakk ，其中 n 的因子个数为： (a1+1)∗(a2+1)∗...∗(ak+1) 首先预处理出1-10^6里面所有的素数，然后枚举这些素数，在枚举[L,R]区间中这些素数的倍数，然后根据这些倍数进行素因子分解，其实就是统计[L,R]区间中有多少个枚举的素数，然后乘以K， 在加 1 计算即可。在枚举 [L,R]区间值的时候，我们需要先把 [L,R] 区间中的数用数组保存下来，然后通过数组进行素因子分解。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 998244353; const LL MAXN = 1e6 + 5; int prime[MAXN], cnt; LL p[MAXN]; void isprime() { memset(prime, 0, sizeof(prime)); cnt = 0; prime[1] = 1; for (LL i = 2; i < MAXN; i++) { if (!prime[i]) { p[cnt++] = i; for (LL j = i * i; j < MAXN; j += i) { prime[j] = 1; } } } } LL f[MAXN], num[MAXN]; int main() { isprime(); int T; scanf("%d", &T); while (T--) { LL L, R, K; scanf("%lld%lld%lld", &L, &R, &K); LL ans = 0; if (L == 1) { ans = 1, L++; } int t = R - L; for (int i = 0; i <= t; i++) { f[i] = i + L, num[i] = 1; } for (int i = 0; i < cnt && p[i]*p[i] <= R; i++) { LL tmp = L; if (L % p[i]) { tmp = (L / p[i] + 1) * p[i]; } for (LL j = tmp; j <= R; j += p[i]) { LL cnt = 0; while (f[j - L] % p[i] == 0) { cnt++; f[j - L] /= p[i]; } num[j - L] = num[j - L] * (cnt * K + 1) % MOD; } } for (int i = 0; i <= t; i++) { if (f[i] == 1) { ans = (ans + num[i]) % MOD; } else { ans = (ans + num[i] * (K + 1)) % MOD; } } printf("%lld\n", ans); } return 0; }