題目描述

給定正整數 $n$，求 $1\le x,y\le n$ 且 $\gcd (x,y)$ 為素數的數對 $(x,y)$ 有多少對。

輸入格式

只有一行一個整數，代表 $n$。

輸出格式

一行一個整數表示答案。

輸入輸出樣例 #1

輸入 #1

4

輸出 #1

4

說明/提示

樣例輸入輸出 1 解釋

對于樣例，滿足條件的 $(x,y)$ 為 $(2,2)$，$(2,4)$，$(3,3)$，$(4,2)$。

---

數據規模與約定

• 對于 $100\%$ 的數據，保證 $1\le n\le 10^7$。

---

來源：bzoj2818。

本題數據為洛谷自造數據，使用 CYaRon 耗時 $5$ 分鐘完成數據制作。

solution

• 若 gcd(x,y) = p 則 x，y 均為 p 的倍數，且其余部分互質。
  • 1 若 $x=p?p_x,[1,p_x]$ 中和 $p_x$ 互質的有 $?(x)$ 個(歐拉函數)，即
    $$\sum _{p<=n}\sum _{i=1}^{n/p}(?(i)?2?1)$$
  • 2 例如 $n=4時，p=2,[?(1)+?(2)]?2?1=3。p=3,?(1)?2?1=1$
• 具體：
  • 1 篩選出質數 p, 并算出 $?(i),i\in [1,n]$
  • 2 遍歷質數，統計個數

代碼

#include "cstring"
#include "string"
#include "algorithm"
#include "iostream"
#include "vector"
#include "unordered_set"
#include "unordered_map"
#include "bitset"
#include "queue"
#include "set"using namespace std;/**  P2568 GCD*  題目大意：給定正整數 n，求 1≤x,y≤n 且 gcd(x,y) 為素數的數對 (x,y) 有多少對。*  思路: 若 gcd(x,y) = p 則 x，y 均為 p 的倍數，且其余部分互質。*  1 若 x = p * px, [1, px] 中和 px 互質的有 phi(x) 個，即 sum(p, sum(phi(px))*2-1) i=[1,n/p]*  2 例如 n = 4,  p = 2  [phi(1) + phi(2)] * 2-1 = 3   p = 3 phi(1)*2 - 1 = 1*  具體：*  1 篩選出質數p, 并算出 phi(i) i=1,n*  2 遍歷質數，統計個數**/const int N = 1e7 + 5, M = 2e6, INF = 1e9, MOD = 0;
typedef long long ll;int prime[N], n, k, f[N], np[N];int main() {cin >> n;// 1 篩選出 n 以內所有質數, 和歐拉函數 f[x]f[1] = 1;for (int i = 2; i <= n; i++) {if (!np[i]) prime[++k] = i, f[i] = i - 1;else f[i] = (i / np[i] % np[i] == 0) ? f[i / np[i]] * np[i] : f[i / np[i]] * (np[i] - 1);for (int j = 1; j <= k && prime[j] * i <= n; j++) {np[i * prime[j]] = prime[j];if (i % prime[j] == 0) break;}}ll ans = 0;for (int i = 1; i <= k; i++) {for (int j = 1; j * prime[i] <= n; j++)ans += f[j] * 2;ans--;}cout << ans;return 0;
}

結果