数论

\(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的两个整数)个数