免费行情网站下载大全php开发网站优势
补题：
题目详情 - 9.段坤爱取模%%% - SUSTOJ
本题或许是参考 Problem - C - Codeforces
根据题意，f(i)就是不能被整除的最小的一个质因子。
打表发现，当15个质因子相乘后，长度就大于18。
因此可以知道小于等于1e16内的正整数x，f(x)一定是前20个质因子之一，且合数一定不行。
前20个质因子：2 3 5 7 11 13 17 19 23 29 31 37 41 43 。在第15个质因子相乘时就大于1e16，因此max(f(i))是小于40的。
现在就是要求：第1个质因子在[l, r]的个数 乘上 第1个质因子，加上 第2个质因子在[l, r]的个数 乘上 第2个质因子个数， … 。需要保证i在[l, r]内仅且一次被计算。考虑容斥。
对于f(i) = k来说，i可以被1 ... k - 1任何一个整除，但是不能被k整除。
f()值为k的个数有：
⌊ r l c m ( 1 , . . . k − 1 ) − r l c m ( 1 , . . . k ) ⌋ − ⌊ l l c m ( 1 , . . . k − 1 ) − l l c m ( 1 , . . . k ) ⌋ \lfloor { \frac {r} {lcm(1, ... k-1)} } - { \frac {r} {lcm(1, ... k)} } \rfloor - \lfloor { \frac {l} {lcm(1, ... k-1)} } - { \frac {l} {lcm(1, ... k)} } \rfloor ⌊lcm(1,...k−1)r−lcm(1,...k)r⌋−⌊lcm(1,...k−1)l−lcm(1,...k)l⌋
如果将[l, r]分成两部分[1, l]和[1, r]来处理的话。
以r为例，f()为k的个数：
⌊ r l c m ( 1 , . . . k − 1 ) − r l c m ( 1 , . . . k ) ⌋ \lfloor { \frac {r} {lcm(1, ... k-1)} } - { \frac {r} {lcm(1, ... k)} } \rfloor ⌊lcm(1,...k−1)r−lcm(1,...k)r⌋
那么，[1, r]内sum就是：
∑ k ≥ 2 k × ( ⌊ r l c m ( 1 , . . . k − 1 ) − r l c m ( 1 , . . . k ) ⌋ ) = 2 × ( r − ⌊ r l c m ( 1 , 2 ) ⌋ ) + 3 × ( ⌊ r l c m ( 1 , 2 ) − r l c m ( 1 , 2 , 3 ) ⌋ ) + . . . = r + ∑ k ≥ 1 ⌊ r l c m ( 1 , . . . , k ) ⌋ \sum_{k \ge 2}k \times(\lfloor { \frac {r} {lcm(1, ... k-1)} } - { \frac {r} {lcm(1, ... k)} } \rfloor) \\ = 2 \times (r - \lfloor \frac r {lcm(1,2)} \rfloor) + 3 \times (\lfloor { \frac {r} {lcm(1,2)} } - { \frac {r} {lcm(1,2,3)} } \rfloor) + ... \\ = r + \sum_{k \ge 1} \lfloor \frac r {lcm(1, ..., k)} \rfloor k≥2∑k×(⌊lcm(1,...k−1)r−lcm(1,...k)r⌋)=2×(r−⌊lcm(1,2)r⌋)+3×(⌊lcm(1,2)r−lcm(1,2,3)r⌋)+...=r+k≥1∑⌊lcm(1,...,k)r⌋
同理，可得[1, l]内的sum，两者相减即为答案。对于cf上的C，[1, r]即可。
时间复杂度：前面稠密，后面稀疏，最大为O(41 * 2)。
const int mod = 998244353;
// https://codeforces.com/contest/1542/problem/C
void solve() {int l,r; cin>>l>>r;int sum = 0;int v = 1;auto lcm = [&](int a, int b) {return a * b / __gcd(a,b);};for(int i = 1; v <= r; v = lcm(i, v), ++i) {sum = (sum + r / v) % mod;}v = 1;for(int i = 1; v <= l - 1; v = lcm(i,v), ++i) {sum = (sum - (l - 1) / v + mod) % mod;}cout<<sum<<endl;
}
总结
赛时对这题容斥没有找到切入点。这个容斥处理极具有思维性，还是需要多做思维题！
参考：
[Codeforces] number theory (R1600) Part.11 - 知乎 (zhihu.com)
Submission #121200660 - Codeforces