乘法逆元

对于1~n所有数字的lcm,应该是1~n中所有质数P的 以P为底数对于n的对数 次幂的乘积

即 lcm = ∏ p^log_pn   。

码题集OJ-跑步 (matiji.net)

线性筛  + 乘法逆元

由题意，1~n每个人最后都重新一起在终点相遇时间停止，那么终止时间则为1~n的所有lcm,

根据上面方法，得到结束的t后，我们再来算每个人在途中会和多少人相遇,我们可以知道每个

人跑的圈数为t / i,，我们把相遇看作成追击问题，他只能追上比自己慢的人，即第i个人，可以

和第 i + 1 ~  n 个人相遇,假设a在追击b，那么他们在t时刻能相遇的次数为t/a - t/b ，那么这些

人追上的次数总和为(n - i) * (t / i) - sum(t / j),j €(i + 1,n),这是他能提供的贡献，对于1~n的所有

人，我们可以帮他的贡献分成两部分，一部分是正贡献，可以追上(i + 1,n)个人，可以被(1,i - 1)

个人追上的负贡献，那么对于第i个人的贡献，他的总贡献为(t / i) * (n - 2 * i + 1),最后累加每个人

的贡献即可求出答案，

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 #define ll long long
 5 #define endl '\n'
 6 #define all(a) a.begin(), a.end()
 7 #define pb push_back
 8 #define cy cout << "YES" << endl
 9 #define cn cout << "NO" << endl
10 #define x first
11 #define y second
12 #define rep(i, l, r) for (int i = l; i <= r; i++)
13 #define debug(_x) cout << #_x << '=' << _x << endl
14 typedef pair<int, int> PII;
15 const double eps = 1e-8;
16 const double pi = acos(-1);
17 const int mod = 998244353;
18 const int N = 1e7 + 10;
19 
20 bool vis[N];
21 int inv[N];
22 vector<int> primes;
23 
24 void solve()
25 {
26     int n;
27     cin >> n;
28     int lcm = 1;
29     // 求以a为底数b的对数
30     auto mylog = [&](int a, int b)
31     {
32         return floor(log(b) / log(a));
33     };
34     auto qsm = [&](int a, int b)
35     {
36         int res = 1;
37         while (b)
38         {
39             if (b & 1)
40                 res = res * a % mod;
41             a = a * a % mod;
42             b >>= 1;
43         }
44         return res;
45     };
46     inv[1] = 1;
47     int ans = 0;
48     for (int i = 2; i <= n; i++)
49     {                                                  // 线性筛求质数
50         inv[i] = (mod - mod / i) * inv[mod % i] % mod; // 线性逆元
51         if (!vis[i])
52         {
53             primes.pb(i);
54             lcm = lcm * qsm(i, mylog(i, n)) % mod;
55         }
56         for (int p : primes)
57         {
58             if (p * i > n)
59                 break;
60             vis[p * i] = 1;
61             if (i % p == 0)
62                 break;
63         }
64     }
65     for (int i = 1; i <= n; i++)
66     {
67         int cnt = lcm * inv[i] % mod;
68         ans = (ans + cnt * (n - 2 * i + 1) % mod + mod) % mod;
69     }
70     cout << ans % mod << endl;
71 }
72 signed main()
73 {
74     ios::sync_with_stdio(false);
75     cin.tie(nullptr);
76     int _ = 1;
77     // cin >> _;
78 
79     while (_--)
80         solve();
81 
82     return 0;
83 }