CF1627D Not Adding

题目描述

题目传送门

思路

看到 $10^6$ 的数据很容易想到枚举每一个可能的 $\gcd(i,j)$ 的值，

对于枚举的值，我们可以枚举其倍数（因为只有其倍数与其的 $\gcd$ 可能为其本身），

这样我们就可以算出其与其所有存在的倍数的 $\gcd$，如果这个值是其本身，那就让 $Ans$ 加上 $1$

这样子出来的数包括了输入中的 $n$ 个,

所以答案为 $Ans - n$

代码

#include <bits/stdc++.h>
using namespace std;

int N;
int A[1000010];
bool Vis[1000010];
int Mx , Ans;

template<class T>
inline char read(T &ret) {
	ret = 0;
	short f = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		ret = (ret << 3) + (ret << 1) + c - 48;
		c = getchar();
	}
	ret *= f;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	read(N);
	for(int i = 1; i <= N; i++) {
		read(A[i]);
		Mx = max(A[i] , Mx);
		Vis[A[i]] = true;
	}
	for(int i = 1; i <= Mx; i++) {
		int Gcd = 0;
		for(int j = i; j <= Mx; j += i) {
			if(Vis[j] == false) continue;
			Gcd = __gcd(Gcd , j);
		}
		if(Gcd == i) Ans++;
	}
	cout << Ans - N << endl;
	return 0;
}