数论
模运算
\(a\%b = a-b*floor(\frac ab)\)
费马小定理
\(a^{p-1} \% p=1\)
最小公倍数&最大公约数
(a,b)表示最大公约数
[a,b]表示最小公倍数
\((a,b)*[a,b] = ab\)
辗转相除
if (a % b==0) return b;
else return gcd(b, a % b);
质数
筛法
for (int i = 2; i <= n; i++) {
if (is_prime[i])
for (int j = 2*i; j <= n; j+=i) is_prime[j]=false; //筛去当前素数的倍数
}
欧拉函数 \(\phi\)
求互质(公约数只有1的两个整数)个数
标签：ab,return,数论,最小,公倍数,最大公约数 From： https://www.cnblogs.com/codaaaa/p/17675372.html