題目鏈接
題意就不多說了

思路

• 滿足條件的只有素?cái)?shù)和素?cái)?shù)組合，因?yàn)樗財(cái)?shù)和非素?cái)?shù)的gcd = 1，兩個(gè)數(shù)除以1之后，不能保證全為素?cái)?shù)。
• 知道只有素?cái)?shù)組合之后，每次判斷最大的素?cái)?shù)，加入當(dāng)前素?cái)?shù)長(zhǎng)度為len，那么這個(gè)最大的素?cái)?shù)一共可以和len - 1個(gè)素?cái)?shù)結(jié)合，因?yàn)榭赡艽嬖谒財(cái)?shù)的倍數(shù)，所以一共可以有 (len - 1) * (n / 素?cái)?shù)）
• 知道思路之后，for循環(huán)跑一下就ok

后記

比賽的時(shí)候想的復(fù)雜了，還好隊(duì)友a(bǔ)了。。。

#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <map> #include <bitset> #include <set> #include <string.h> #include <cmath> #include <queue> #include <algorithm> #define N 10000005 #define ll long long #define lowbit(a) a&(-a) #define pb(a) push_back(a) #define mk(a, b) make_pair(a, b) #define mem(a, b) memset(a, b, sizeof(a)) #define read(a) scanf("%d", &a) #define print(a) printf("%d\n", a) using namespace std; int vis[N]; int main(){#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifmem(vis, -1);vis[0] = vis[1] = 0;// 素?cái)?shù)打表for (ll i = 2; i < N; ++i) {if (vis[i] == -1) {for (ll j = i * i; j < N; j += i) {vis[j] = 0;}}}int n;while(cin >> n) {vector<int> v;int len = 0;// 降序?qū)⑺財(cái)?shù)push到vector中for (int i = n; i >= 2; --i) {if (vis[i] == -1) v.push_back(i), ++len;}ll ans = 0;ll sum = len - 1;// 循環(huán)加for (int i = 0; i < len; ++i) {ans += (sum--) * (n / v[i]);}cout << ans * 2 << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客网暑期ACM多校训练营（第三场）H - Diff-prime Pairs的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。