网站建设水平如何评价,外贸网站关键词优化,企业网站设计注意事项,代做ansys网站补题#xff1a;
题目详情 - 9.段坤爱取模%%% - SUSTOJ
本题或许是参考 Problem - C - Codeforces
根据题意#xff0c;f(i)就是不能被整除的最小的一个质因子。
打表发现#xff0c;当15个质因子相乘后#xff0c;长度就大于18。 因此可以知道小于等于1e16内的正整数x…补题
题目详情 - 9.段坤爱取模%%% - SUSTOJ
本题或许是参考 Problem - C - Codeforces
根据题意f(i)就是不能被整除的最小的一个质因子。
打表发现当15个质因子相乘后长度就大于18。 因此可以知道小于等于1e16内的正整数xf(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⌋)...rk≥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; cinlr;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;}coutsumendl;
}总结
赛时对这题容斥没有找到切入点。这个容斥处理极具有思维性还是需要多做思维题
参考
[Codeforces] number theory (R1600) Part.11 - 知乎 (zhihu.com)
Submission #121200660 - Codeforces
