Codeforces Round #766 (Div. 2)补题 E.Not Adding 数论GCD

题目大意

给定序列 { a 1 , a 2 , … , a n } \{a_1,a_2,\dots , a_n\} {a1​,a2​,…,an​}，包含 n n n个不同的整数。每次可以从序列中选择两个元素 a i a_i ai​和 a j a_j aj​(要求 gcd ⁡ ( a i , a j ) \gcd(a_i, a_j) gcd(ai​,aj​)不位于序列中)，将他们从序列中删除，同时将 gcd ⁡ ( a i , a j ) \gcd(a_i, a_j) gcd(ai​,aj​)插入序列中。求最大的操作次数。

思路

首先，原序列中任意数字的 gcd ⁡ \gcd gcd一定小于序列中的最大值，即 gcd ⁡ ( ∀ ( a i , a j ) { a 1 , a 2 , … , a n } ) ≤ max ⁡ ( { a 1 , a 2 , … , a n } ) \gcd(\forall(a_i, a_j)\{a_1, a_2, \dots, a_n\}) \leq \max(\{a_1, a_2, \dots, a_n\}) gcd(∀(ai​,aj​){a1​,a2​,…,an​})≤max({a1​,a2​,…,an​})，且对于操作后的子集仍然成立。

那么我们可以假设将 [ 1 , max ⁡ ( { a 1 , a 2 , … , a n } ) ] [1, \max(\{a_1, a_2, \dots, a_n\})] [1,max({a1​,a2​,…,an​})]中的所有数字都加入集合中来，然后判断每个数究竟能否出现在集合中。

考虑某个数 x x x如何出现在序列中：

1. x ∈ { a i } x \in \{a_i\} x∈{ai​}
2. x ∈ s u b s e t gcd ⁡ { a i } x \in subset_{\gcd}\{a_i\} x∈subsetgcd​{ai​}（ x x x是通过 gcd ⁡ \gcd gcd操作得到的 a a a的子集中的元素）

那么显然第二种情况的 x x x是通过 gcd ⁡ ( a m , a n , a p , …   ) \gcd(a_m, a_n, a_p,\dots) gcd(am​,an​,ap​,…)得到的，那么一定存在 a j ∈ { a i } a_j \in \{a_i\} aj​∈{ai​}使得 a j a_j aj​是 x x x的倍数。

所以我们可以枚举 x x x的所有倍数，对于每个存在于 a a a序列中的倍数 x i x_i xi​求 gcd ⁡ ( x i , gcd ⁡ i − 1 ) \gcd(x_i, \gcd_{i-1}) gcd(xi​,gcdi−1​)，如果最终的 gcd ⁡ \gcd gcd结果是 x x x，那么代表 x x x一定能被凑出来，也就是 x x x会以第二种方式出现在集合中。我们从 [ 1 , max ⁡ ( { a 1 , a 2 , … , a n } ) ] [1, \max(\{a_1, a_2, \dots, a_n\})] [1,max({a1​,a2​,…,an​})]统计所有满足条件的 x x x。

额外注意，因为第一种情况( x x x本身存在于 a a a序列中)，所以在枚举的过程中一定会多统计 n n n个 x x x，所以最终结果减去 n n n个 x x x。

Accepted Code

#include 
using namespace std;

const int N = 1e6 + 10;
int a[N];

inline void solve(){
    int n = 0, maxx = -1, ans = 0; cin >> n;
    for(int i = 1; i > x;
        maxx = max(maxx, x), a[x]++;
    }
    for(int i = 1; i