GCDs
5.【题解】Same GCDs
题解 思路 计算有多少个 \(x(0\leq x<m)\) 使得 \(\gcd(a,m)=\gcd(a+x,m)\) 事实上就是求有多少个 \(x(1\leq x\leq m)\) 使得 \(\gcd(x,m)=\gcd(a,m)\) 所以可以将 \(m\) 除以 \(\gcd(a,m)\) ,于是 ......
[ARC124C] LCM of GCDs 题解
题目跳转 Fake_Solution 前言 [warning]: 本题解的做法是错法,但是正确概率贼高。离谱的是正确率还可以叠加。 正解是记搜,时间复杂度可以证明。正解看文末。 思考 众所周知一个公式: \[a\times b=\operatorname{lcm}(a,b)\times \gcd(a ......