Counting Divisors

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

题意：给你l，r和k，求出题目中给出的式子，其中d（n）表示n的因子个数

解题思路：根据约数个数定理，d(i^k) = (k*c1 + 1) * (k*c2 + 1) * ... * (k*cj + 1)，其中i = p1^c1*p2^c2*...*pj^cj，pj为i的质因子。因为题目范围为1e12，所以只需要打出1e6的素数表即可，然后暴力枚举每个素数，找出是这个素数的倍数的数字，然后求出每个数字的贡献即可（最后可能有数字并没有处理完，因为只有1e6的素数表，所以最后还需要进行处理）

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; const LL mod = 998244353; bool vis[1000009]; LL prime[1000009], sum[1000009], a[1000009]; LL l, r, k; int cnt; void init() { memset(vis, true, sizeof vis); vis[0] = vis[1] = false; cnt = 0; for (int i = 2; i < 1000009; i++) { if (!vis[i]) continue; prime[cnt++] = i; for (int j = i * 2; j < 1000009; j += i) vis[j] = false; } } int main() { init(); int t; scanf("%d", &t); while (t--) { scanf("%lld%lld%lld", &l, &r, &k); for (int i = 0; i <= r - l; i++) sum[i] = 1, a[i] = i + l; LL ans = 0; for (int i = 0; i < cnt; i++) { LL p = (l / prime[i] + (l%prime[i] ? 1 : 0))*prime[i]; for (LL j = p; j <= r; j += prime[i]) { int res = 0; while (a[j - l] % prime[i] == 0) res++, a[j - l] /= prime[i]; sum[j - l] = sum[j - l] * ((1LL * res*k + 1) % mod) % mod; } } for (int i = 0; i <= r - l; i++) { if (a[i] != 1) sum[i] = sum[i] * (k + 1) % mod; ans = (ans + sum[i]) % mod; } printf("%lld\n", ans); } return 0; }