首页 > 其他分享 >CF1285F Classical?

CF1285F Classical?

时间:2023-07-20 18:33:19浏览次数:37  
标签:CF1285F gcd limits max sum mid Classical text

根据唯一分解定理,令 \(x=p_1^{q_1}p_2^{q_2}\cdots p_m^{q_m},y=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\),则 \(\text{lcm}(x,y)=p_1^{\max(q_1,k_1)}p_2^{\max(q_2,k_2)}\cdots p_m^{\max(q_m,k_m)}\)。那么一定存在 \(i\mid x,j\mid y\),使得 \(\text{gcd}(i,j)=1\) 且 \(\text{lcm}(i,j)=\text{lcm}(x,y)\),因为如果对每个 \(p_i\) 考虑的话,如果 \(q_i\ge k_i\),把 \(p_i^{\max(q_i,k_i)}\) 给 \(i\),否则给 \(j\) 即可。

令值域为 \(A\le 10^5\)。考虑到 \(a_i\le A\),于是枚举 \(d\mid a_i\) 加入集合 \(S\),即求 \(\max\limits_{x,y\in S}xy[\gcd(x,y)=1]\),显然去重后 \(|S|\le A\)。

发现如果 \(x<y\) 且 \(\gcd(x,y)=1\),那么 \(\forall x<z<y\),\(xz<xy\),所以 \(z\) 实际上对答案没有贡献。所以我们从大到小枚举 \(x\) 并加入一个栈中,如果加入栈之前里面有 \(\gcd(x,y)=1\) 的 \(y\),那么我们从栈顶一直 pop 到 \(y\),中间所有数都对答案没有贡献。\(y\) 对答案的贡献就是 \(xy\)。

如果我们知道栈里有与 \(x\) 互质的数就可以直接弹栈,均摊是 \(O(n)\) 的,考虑快速判断栈里有没有与 \(x\) 互质的数。

显然这样的数的个数是 \(f(x)=\sum\limits_{i=1}^{A}c_i[\gcd(i,x)=1]\),\(c_i\) 表示栈中 \(i\) 这个数的个数,去重后为 \(0/1\)。然后就是 classical 的了:

\[\begin{aligned}f(x)&=\sum\limits_{i=1}^{A}c_i[\gcd(i,x)=1]\\&=\sum\limits_{i=1}^Ac_i\sum\limits_{d\mid i,d\mid x}\mu(d)\\&=\sum\limits_{d\mid x}\mu(d)\sum\limits_{d\mid i} c_i\end{aligned} \]

令 \(t_d=\sum\limits_{d\mid i}c_i\) 为 \(d\) 的倍数在栈中的个数。

\[f(x)=\sum\limits_{d\mid x}\mu(d)t_d \]

求一遍 \(f(x)\) 是 \(O(d(x))\) 的,弹栈的时候动态维护 \(f(x)\) 和 \(t_i\) 的值即可。复杂度 \(O(\sum\limits_{i=1}^Ad(i))=O(A\log A)\)。

如果没观察到一开始的那个性质,直接枚举 \(\gcd(x,y)\) 也可以做到 \(O(A\log^2 A)\)。

提交记录。

标签:CF1285F,gcd,limits,max,sum,mid,Classical,text
From: https://www.cnblogs.com/Ender32k/p/17569340.html

相关文章

  • Graph Neural Networks Inspired by Classical Iterative Algorithms
    目录概符号说明MotivationRobustRegularizationYangY.,LiuT.,WangY.,ZhouJ.,GanQ.,WeiZ.,ZhangZ.,HuangZ.andWipfD.Graphneuralnetworksinspiredbyclassicaliterativealgorithms.ICML,2021.概基于广义energyfunction(diffusion)的图神经网......
  • algrothm_classical
    ......
  • CF1285F
    枚举\(\gcd\),对除\(\gcd\)后互质的数对求贡献。从大到小枚举\(a_i\),那么对于\(x<z<y\),且\((x,y)=1\),那么\(z\)和\(y\)都不会在余下的数中产生有价值的......
  • Classical Cipher
    [NPUCTF2020]ClassicalCipher难得做到一道古典密码的题目,打开后有一个flag.zip和一个提示。解密后的flag请用flag{}包裹压缩包密码:gsv_pvb_rh_zgyzhs对应明文:***......