1.5 \(s / 64\) \(MB / 140\) points

There is a planet, in a yet undiscovered part of the universe, with a country inhabited solely

by mathematicians. In this country, there are a total of \(N\) mathematicians, and the interesting

fact is that each mathematician lives in their own city. Is it also interesting that no two cities

are connected with a road, because mathematicians can communicate online or by

reviewing academic papers. Naturally, the cities are labeled with numbers from 1 to \(N\) .

Life was perfect until one mathematician decided to write an academic paper on their

smartphone. The smartphone au\(to-co\)rrected the word “se\(lf-ev\)ident” to “Pictionary” and the

paper was published as such. Soon after, the entire country discovered pictionary and

wanted to meet up and play, so construction work on roads between cities began shortly.

The road construction will last a total of \(M\) days, according to the following schedule: on the

first day, construction is done on roads between all pairs of cities that have \(M\) as their

greatest common divisor. On the second day, construction is done on roads between all

pairs of cities that have \(M-1\) as their greatest common divisor, and so on until the \(M\) ^{th} day

when construction is done on roads between all pairs of cities that are \(co-pr\)ime. More

formally, on the \(i\) ^{th} day, construction is done on roads between cities \(a\) and \(b\) if gcd(a, b) = M

• \(i + 1\) .

Since the mathematicians are busy with construction work, they’ve asked you to help them

determine the minimal number of days before a given pair of mathematicians can play

pictionary together.

In test cases worth 40% of total points, it will hold \(N\) ≤ 1000, \(Q\) ≤ 100 000.

1.5 \(s / 64\) \(MB / 140\) points

The first line of input contains three positive integers N, M and \(Q\) (1 ≤ \(N\) , \(Q \le 100\,000\), 1 ≤ \(M\)

≤ \(N\) ), the number of cities, the number of days it takes to build the roads, and the number of

queries.

Each of the following \(Q\) lines contains two distinct positive integers \(A\) and \(B\) (1 ≤ \(A\) , \(B\) ≤ \(N\) )

that denote the cities of the mathematicians who want to find out the minimal number of days

before they can play pictionary together.

The \(i\) ^{th} line must contain the minimal number of days before the mathematicians from the \(i\) ^{th}

query can play pictionary together.

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 5