题解#B. Integral Array#

题解：

这题我们可以通过枚举，把所有c上的数字都跑一边，寻找是否存在结果。

这时候我们就发现，对于第i个数字，他的 $[i * k - 1, i * k - i]$ 范围对于i而言除数结果是相同的，只要判定这个范围是否有数字，就判定一次k是否存在序列里即可。

因此这里要用一个简单的前缀和记录数字是否存在。

此时时间复杂度就是 $c * l o g (c)$

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int vis[maxn];
int mmm[maxn];
int main() {
	int t = 0;
	cin >> t;
	while (t--) {
		int n, c, x;
		cin >> n >> c;
		for (int i = 1; i <= n; i++) {
			cin >> x;
			vis[x] = 1;
			mmm[x] = 1;
		}
		for (int i = 1; i <= c; i++)
		{
			vis[i] += vis[i - 1];
		}
		int f = 0;
		for(int i =1 ; i<= c ; i ++){
			if (mmm[i] == 0)continue;
			for (int j = i * 2; j <= c; j += i) {
				if (vis[j - 1] - vis[max(j - i - 1,0)]) {
					if (mmm[(j-1) / i] == 0) {
						f = 1;
					}
				}
			}
			if (vis[c] - vis[max(c / i * i - 1,0)]) {
				if (mmm[c / i] == 0) {
					f = 1;
				}
			}


		}
		if (f == 0)cout << "YES\n";
		else cout << "No\n";
		for (int i = 1; i <= c; i++)vis[i] = 0,mmm[i] = 0;
	}

}

题解#B. Integral Array#

tag:

题解：

代码：