欧拉筛 – Tgotp-Blog

2818: Gcd

首先知道

gcd(x,y) =  z

可化为

gcd(x/z,y/z) = 1;

那么令f[i] 为满足 gcd(x,y)= 1 (x,y <= i)的个数

那么答案就为 ∑ f[n/prime[i]]

观察发现 f[i] 为欧拉函数的前缀和。

那么线[……]

Read more

欧拉筛 & 矩阵乘法 & 矩阵快速幂