1. 首頁 > 生活百科 > >

Pictionary 方法記錄

生活百科

[COCI2017-2018#5] Pictionary題面翻譯題目描述在宇宙一個不為人知的地方，有一個星球，上面有一個國家，只有數學家居住 。在這個國家有\(n\)個數學家 ， 有趣的是，每個數學家都住在自己的城市，且城市間無道路相連，因為他們可以在線交流 。當然，城市有從\(1\)到\(n\)的編號 。
一位數學家決定用手機發論文，而手機將“不言而喻”自動更正成了“猜謎游戲” 。不久之后，這個國家就發現了猜謎游戲 。他們想要見面一起玩，于是這個國家就開始了修路工程 。道路修建會持續\(m\)天 。對于第\(i\)天，若\(\gcd(a,b)=m-i+1\)，則\(a\)和\(b\)城市間會修一條路 。
由于數學家們忙于建筑工作，請你來確定一對數學家最早什么時候能湊到一起玩 。
輸入輸出格式輸入格式第一行有三個正整數\(n,m,q\)，表示城市數量、修路持續天數、詢問數量 。接下來\(q\)行，每行有兩個正整數\(a,b\)，表示詢問\(a\)和\(b\)兩個城市的數學家最早什么時候能在一起玩 。
輸出格式輸出\(q\)行，第\(i\)行有一個正整數，表示第\(i\)次詢問的結果
說明【Pictionary 方法記錄】數據范圍：對于\(40\%\)的數據：\(n≤4000,q≤10^5\)對于全部數據：\(1≤n,q≤10^5\)\(1≤m≤n\)
樣例1解釋：在第一天，\((3,6)\)之間修了一條路，因此第二次詢問輸出1在第二天，\((2,4),(2,6),(2,8),(4,6),(6,8)\)之間都修了一條路，此時\(4\)和\(8\)號城市連通，第三次詢問輸出2在第三天，所有編號互質的城市之間都修了路，\(2\)和\(5\)號城市在此時連通，第一次詢問輸出1
樣例2解釋：在第二天，\((20,15)\)之間修了一條路第四天，\((15,9)\)之間修了一條路所以\(20\)和\(9\)號城市在第四天連通，輸出4
題目描述There is a planet, in a yet undiscovered part of the universe, with a country inhabited solelyby mathematicians. In this country, there are a total of ?N mathematicians, and the interestingfact is that each mathematician lives in their own city. Is it also interesting that no two citiesare connected with a road, because mathematicians can communicate online or byreviewing 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 theirsmartphone. The smartphone auto-corrected the word “self-evident” to “Pictionary” and thepaper was published as such. Soon after, the entire country discovered pictionary andwanted 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 thefirst day, construction is done on roads between all pairs of cities that have ?M as theirgreatest common divisor. On the second day, construction is done on roads between allpairs of cities that have ?M-1 as their greatest common divisor, and so on until the ?\(M^{th}\) daywhen construction is done on roads between all pairs of cities that are co-prime. Moreformally, 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 themdetermine the minimal number of days before a given pair of mathematicians can playpictionary together.
輸入格式The first line of input contains three positive integers ?N, Mand ?Q(1 ≤ ?N, ?Q ≤ 100 000, 1 ≤ ?M≤ ?N), the number of cities, the number of days it takes to build the roads, and the number ofqueries.
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 daysbefore 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.
樣例 #1樣例輸入 #18 3 32 53 64 8樣例輸出 #1312樣例 #2樣例輸入 #225 6 120 9樣例輸出 #24樣例 #3樣例輸入 #39999 2222 21025 24053154 8949樣例輸出 #319802160提示In test cases worth 40% of total points, it will hold ?N≤ 1000, ?Q≤ 100 000.
Clarification of the first test case:
On the first day, road (3, 6) is built. Therefore the answer to the second query is 1.
On the second day, roads (2, 4), (2, 6), (2, 8), (4, 6) and (6, 8) are built. Cities 4 and 8 are nowconnected (it is possible to get from the first to the second using city 6).
On the third day, roads between relatively prime cities are built, so cities 2 and 5 are connected.
Clarification of the second test case:
On the second day, road (20, 15) is built, whereas on the fourth day, road (15, 9) is built. After thefourth day, cities 20 and 9 are connected via city 15.

推薦閱讀