蓝桥杯2022年第十三届决赛真题-齿轮
摘要：解题思路:通过列出算式 q=a1/a2*a2/a3*a3......an-2/an-1*an-1/an发现可以约掉中间部分只剩下头尾得到q=a1/an阅读题目发现q为整数,那么可得 a1%an=0且a……
分解约数，O(n^1.5)
摘要：原题题意转换为，对每个询问x，查询序列中是否存在两个整数a,b，使得a/b=x（特别地，当只有一个齿轮时，x可以为1）可以直接对所有结果为"YES"的x进行预处理。首先若b可被a整除，那么必有a<=b……
蓝桥杯2022年第十三届决赛真题-齿轮(复杂度O(qlnq))
摘要：解题思路:枚举所有倍数下的所有半径，判断是否存在两个半径为此倍数。注意事项:枚举半径只到max(qi,ri)/i,总共进行∑q/i次，类比调和级数调，故复杂度近似O(qlnq)。参考代码:#inclu……
蓝桥杯2022年第十三届决赛真题-齿轮
摘要：解题思路:先把半径排序，把每个半径i进行约数分解，如果半径i的某个约数是之前出现过的半径j（j<=i）, 则i/j倍可行，由于i/j也是i的约数，所以j倍也可行。注意事项:输入要用scanf，用cin……