[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\)次询问的结果
说明数据范围：对于\(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.
经验总结扩展阅读
- 真假烟的快速鉴别方法
- 原神机械之心任务的完成方法是什么
- 眼霜的正确使用顺序,眼霜的正确使用方法
- 鉴别红酒真假最简单三种方法
- 虾滑怎么下火锅
- 穿越火线烟雾保护头怎么调（cf最新调烟雾的方法)
- Programiranje 方法记录
- 晒茄子干最简单的方法
- 竹荪怎么泡发
- 微信如何添加自己好友（找回添加好友记录)