1033. Connecting Through Shared Divisors

Cities are numbered 1 to n. Two cities x and y are DIRECTLY joined when some integer d strictly greater than t divides both of them. Being joined is passed along, so a chain of direct joins puts the cities in one group.

For each of q questions a b, print YES if the two cities are in one group and NO otherwise. A city is always in its own group.

n = 6, t = 2: 3 and 6 -> YES 4 and 6 -> NO 2 and 4 -> NO n = 6, t = 0: everything -> YES n = 6, t = 6: nothing joins, so only a city with itself -> YES n = 10, t = 1: 2 and 4 -> YES 3 and 9 -> YES 2 and 3 -> YES

The first line needs care. With t = 2 the only divisor above 2 that has two multiples inside 1 to 6 is 3, joining 3 and 6. Cities 4 and 6 share the divisor 2, which is not above 2, and no larger divisor divides both. So the answer is NO.

The last line is the opposite surprise: with t = 1, the divisor 2 joins 2, 4, 6, 8, 10 and the divisor 3 joins 3, 6, 9, and city 6 belongs to both, so 2 and 3 end up in one group even though they share nothing at all.

## What most people try first

For every pair of cities, take the greatest common divisor and join when it exceeds t. That is n(n-1)/2 calls, which at n = 2 * 10^5 is 2 * 10^10 divisions.

## Sweep the divisors instead of the pairs

Every direct join is caused by a divisor. So walk the divisors:

for d from t+1 to n: for each multiple m of d with m >= 2d and m <= n: union(d, m)

For a divisor d, all of its multiples share d, so joining each of them to d itself puts the whole lot in one group with n/d - 1 merges rather than with pairs.

The total number of merges is n/(t+1) + n/(t+2) + ... + n/n, which is at most n * (1 + 1/2 + ... + 1/n), about n ln n. At n = 2 * 10^5 that is under 2.5 * 10^6.

## Why joining each multiple to d gives the same groups

Two cities x and y are directly joined exactly when their greatest common divisor exceeds t. If it does, let d be that common divisor: both are multiples of d, so both were joined to d and hence to each other. Going the other way, every union performed is between d and one of its multiples, which do share the divisor d > t, so nothing is joined that should not be.

## The threshold of zero

With t = 0 the sweep starts at d = 1, and 1 divides everything, so city 1 is joined to every other city and the whole range becomes one group. That falls out of the loop with no special case, and it is the case a solution starting the sweep at 2 gets wrong.

## The city 1, when t is at least 1

The only divisor of 1 is 1 itself, which is not above t, so city 1 is joined to nothing and stays alone. A question naming city 1 and anything else answers NO, and city 1 against itself answers YES.

## Overflow

Everything here stays under n, which is 2 * 10^5, far inside a signed 32 bit integer whose maximum is 2147483647. The inner loop must step by d rather than testing every number for divisibility, or the sweep becomes O(n^2).

## Cross-reference

Problem 999 joins values through their prime factors, which is the same idea approached from the other end: there the values are scattered and each is factorised, here the values are every number in a range and the divisors can simply be walked. Read the two together and the choice of direction becomes the lesson.

## Cost

Time O(n log n + q) alpha. Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ t ≤ n` - `1 ≤ q ≤ 200000` - `1 ≤ a, b ≤ n`