本文共 528 字，大约阅读时间需要 1 分钟。
为了解决问题，我们需要计算从1到n的所有数对(i, j)中，i和j的最大公约数为p的数目。通过分析和应用数论中的欧拉函数，我们可以得出以下结论：
问题转化：题目要求计算满足gcd(i, j) = p的数对(i, j)的数量。我们可以将问题转化为寻找互质的数对(a, b)，其中i = p * a，j = p * b。
限制条件：为了满足gcd(i, j) = p，a和b必须互质，并且1 ≤ a, b ≤ n/p。令m = floor(n/p)。
欧拉函数的应用：欧拉函数φ(m)计算小于等于m的自然数中与m互质的数的个数。由于a和b必须互质，每对(a, b)满足条件的次数为φ(1) + φ(2) + ... + φ(m)。
公式推导：因此，满足gcd(i, j) = p的数对个数为φ(1) + φ(2) + ... + φ(m)，即φ(1) + φ(2) + ... + φ(m)。
∑从i = 1到floor(n/p)，再计算每一项φ(i)，即最终的总数为：
∑ i = 1 到 floor(n/p) φ(i)
简化为：
∑_{i=1}^{n/p} φ(i)，其中floor(n/p) = m。因此，答案为欧拉函数从1到m的求和。
转载地址：http://iijrz.baihongyu.com/