775 Div.1 B. integral array mathematics

B
1800

The question

Give an example containing $n$ Sequence of Numbers $a_1,a_2,...,a_n$, And give $c$ , Indicates that the size of all numbers in the sequence does not exceed $c$. We call a sequence integral if and only if for any two of the sequences （ Or the same ） Count $x,y(x\le y)$ , Satisfy $\lfloor \frac{y}{x}\rfloor$ Also in the sequence . Ask whether this sequence is integral .$(n\le 1e6)$

Ideas

The first reaction of this problem is to use a method similar to prime sieve to optimize , Put right $r=\lfloor \frac{y}{x}\rfloor$ Change your judgment to $y$ The judgment of the , It can't be disassembled into $xandr$ ”, So you can enumerate all $x$, And enumerate all $r\notin a$ , If in $x\times r$ The corresponding range exists $y$, be $r=\lfloor \frac{y}{x}\rfloor \notin a$ , Not whole . The corresponding range is $[r\times x,r\times x+x-1]$, Whether there is $y$ Just preprocess the prefix and .
By harmonic series , Time complexity $O(c\log c)$ .

Code

int cnt[maxn], sum[maxn];
void solve() {
    
    int n, c;
    cin >> n >> c;
    for(int i = 1; i <= c; i++) cnt[i] = 0;
	for(int i = 1; i <= n; i++) {
    
		int x;
		cin >> x;
		cnt[x]++;
	}
	sum[0] = 0;
	for(int i = 1; i <= c; i++) {
    
		sum[i] = sum[i-1] + cnt[i];
	}
	for(int x = 1; x <= c; x++) {
    
		if(!cnt[y]) {
    
			continue;
		}
		for(int i = 1; i * x <= c; i++) {
    
			if(cnt[i]) continue;
			int l = i * x - 1;
			int r = min((i+1)*x-1, c);
			if(sum[r] - sum[l]) {
    
				cout << "No\n";
				return;
			}
		}
	}
	cout << "Yes\n";
}