AT3645 GCDロボット


思路根据题意,自然要求 $gcd(A_i , Z)$ ,记为 $B_i$显然 , 与 $Z$ “完全一样”的数一定要是每一个 $B_i$ 的倍数。很显然, $Z$ 的最小取值为 $Lcm(Ans , B_i)$ (Ans 是答案,初值为 $1$)。参考代码#include <bits/stdc

欧拉函数


欧拉函数定义欧拉函数(Euler's totient function),即 $\varphi$,表示的是小于等于 $n$ 和 $n$ 互质的数的个数。$e.g. \ \ \ \varphi(1) = 1$当 $n$ 是质数的时候,显然有 $\varphi(n) = n - 1$。计算若在算数剧本

「P6156 简单题」加强版


题目描述题目传送门思路$$\sum\limits_n\sum\limits_m(i+j) k gcd(i,j) \mu2(gcd(i , j))$$套路枚举 $d$$$= \sum_ n\mu2(d)d\sum_n\sum\limits_m gcd(i,j) = d^k$$换元$$= \sum_ n

CF1627D Not Adding


题目描述题目传送门思路看到 $10^6$ 的数据很容易想到枚举每一个可能的 $\gcd(i,j)$ 的值,对于枚举的值,我们可以枚举其倍数(因为只有其倍数与其的 $\gcd$ 可能为其本身),这样我们就可以算出其与其所有存在的倍数的 $\gcd$,如果这个值是其本身,那就让 $Ans$ 加上 $1$

CF1629B GCD Arrays


题目简述题目传送门给你一个长度为 $N$ 的 $a$ 数组($a$ 数组的元素是 $l$ 到 $r$ 区间中的整数),你可以进行 $k$ 此操作,每次操作可以选择两个数,将他们的乘积加入 $a$ 数组并且删除这两个数,问 $k$ 此操作后能否使 $\gcd(a)$ 大于 $1$思路很容易想到要让每个