Codeforces1648B. Integral Array

传送门

题目大意

一个长为 \(n（1\leq n\leq 10^6)\) 的正整数序列，其中最大的数字不超过 \(c(1\leq c\leq 10^6)\) ，然后对与序列中任意两个数字 \(x,y(x\geq y)\) （ \(x,y\) 可以是同一个数字），都有 $ k = \lfloor \frac{x}{y}\rfloor$ 也在这个序列内，则称这个序列是整的，判断给定的序列是否是整的。

思路

考虑到对于一个序列中的数字 \(j\) 和 一个给定的倍数 \(i\) ，如果序列中存在 \(x\) ，使得 \(ij\leq x<(i+1)j\) ，并且 \(i\) 不在序列之中，那么就说明不行。由于数字的上限 \(c\) 很小，我们可以枚举所有的不在序列中的倍数 \(j\) ，对于每一个 \(j\) ，枚举序列中所有的 \(i*j\leq c\) 的数字 \(i\) ，进行如上判断，如果都能满足，则说明是整的，否则不是。这样枚举的每一个 \(j\) 最多会枚举 \(frac{c}{j}\) 个 \(i\) ，也就是最多枚举 \(clogc\) 次，对于查询是否存在我们可以预处理前缀和 \(O(1)\) 求得，于是总的复杂度为 \(O(clogc)\) 。

代码

#include
#include
#include PII;
#define all(x) x.begin(),x.end()
#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 100000000;
const LL mod = 998244353;
const int maxn = 1000010;

int T, N, C;
int cnt[maxn], A[maxn];

void solve()
{
	for (int i = 1; i <= C; i++)//倍数
	{
		if (cnt[i] - cnt[i - 1])
			continue;
		for (int j = 1; j * i <= C; j++)//数
		{
			if (cnt[j] - cnt[j - 1] == 0)
				continue;
			if (cnt[min(C, (i + 1) * j - 1)] - cnt[i * j - 1])
			{
				cout << "NO" << endl;
				return;
			}
		}
	}
	cout << "YES" << endl;
}

signed main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		cin >> N >> C;
		for (int i = 1; i <= C; i++)
			cnt[i] = 0;
		for (int i = 1; i <= N; i++)
		{
			cin >> A[i];
			cnt[A[i]]++;
		}
		for (int i = 1; i <= C; i++)
			cnt[i] = cnt[i] + cnt[i - 1];
		solve();
	}

	return 0;
}