签到

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <stack>
 9 #include <map>
10 #include <set>
11 #include <cmath>
12 #include <cctype>
13 #include <ctime>
14 
15 using namespace std;
16 
17 #define REP(i, n) for (int i = 0; i < (n); ++i)
18 #define eps 1e-9
19 
20 typedef long long ll;
21 typedef pair<int, int> pii;
22 
23 const int INF = 0x7fffffff;
24 const int maxn = 1.1e6;
25 const ll mod = 998244353;
26 int T, k, prime_cnt = 0, cnt;
27 ll l, r, ans;
28 int prime[maxn];
29 bool vis[maxn];
30 ll ans_t[maxn], a[maxn];
31 
32 void init() {
33     for (int i = 2; i < maxn; ++i) {
34         if (!vis[i]) {
35             prime[prime_cnt++] = i;
36             for (int j = i; j < maxn; j += i) { vis[j] = true; }
37         }
38     }
39 }
40 void cal(int x) {
41     ll l_t, t; t = l / prime[x];
42     if (t * prime[x] == l) { l_t = l; } else { l_t = (t + 1) * prime[x]; }
43     if (l_t > r) { return; }
44 //    printf("prime = %d, l_t = %I64d
", prime[x], l_t);
45     for (ll i = l_t - l; i <= r - l; i += prime[x]) {
46         cnt = 1; a[i] /= prime[x];
47         while (a[i] % prime[x] == 0) { a[i] /= prime[x]; ++cnt; }
48         ans_t[i] *= 1ll * cnt * k + 1; ans_t[i] %= mod;
49     }
50 }
51 
52 int main() {
53 #ifdef __AiR_H
54     freopen("in.txt", "r", stdin);
55 //    freopen("out.txt", "w", stdout);
56 #endif // __AiR_H
57     scanf("%d", &T); init();
58     while (T--) {
59         scanf("%I64d %I64d %d", &l, &r, &k); ans = 0;
60         for (ll i = 0; i <= r - l; ++i) { a[i] = l + i; ans_t[i] = 1; }
61         for (int i = 0; i < prime_cnt; ++i) { cal(i); }
62         for (ll i = 0; i <= r - l; ++i) {
63             if (a[i] != 1) { ans_t[i] *= k + 1; ans_t[i] %= mod; }
64         }
65 //        for (int i = 0; i <= r - l; ++i) {
66 //            printf("i = %d %I64d
", i, ans_t[i]);
67 //        }
68 //        printf("
");
69         for (int i = 0; i <= r - l; ++i) { ans = (ans + ans_t[i]) % mod; }
70         printf("%I64d
", ans);
71     }
72 #ifdef __AiR_H
73     printf("Time used = %.2fs
", (double)clock() / CLOCKS_PER_SEC);
74 #endif // __AiR_H
75     return 0;
76 }
View Code