有一个n <= 10 ^ 6整数的序列,都不超过m <= 3*10 ^ 6,我想计算其中有多少个互质对.如果最大公约数为1,则两个数字是互质的.
它可以在O(n ^ 2 log n)中平凡地完成,但这显然是缓慢的方式,因为限制表明更接近O(n log n).可以快速完成的一件事就是将所有数字分解出来,并且每个数字中都会抛出相同质数的多个出现,但这并没有带来任何显着的改善.我还想过计算相反的 - 具有公约数的对.它可以分组完成 - 首先计算它们最小公共素数除数为2,然后是3,5等的所有对,但在我看来它似乎是另一个死胡同.