CF2043D Problem about GCD

· · 个人记录

CF2043D Problem about GCD

只是想不那么严谨地证一下，之后复习能想起来。

如何求\ge l的数中最小的与x互质的数。

首先，若是把x质因数分解，它的因子一定越小越好，因为这样会使与他不互质的数更密集，所以互质数最少的x的大概是x=2^{ \alpha_1}\cdot3^{\alpha_2}\cdot...\cdot p_n^{\alpha_n}，然后考虑从l开始，假设是i被2筛走（其他情况不会更优），所有l+2,l+4...都被筛走，l+1被3筛走，l+4,l+7...都被3筛走，以此类推，下一个2,3都筛不到的是5，就和筛素数一样，大概到了31这个位置就无法被其他筛掉了，所以大概只会走\log n次，而且这种情况接近于（或者就是）最坏情况，不用细证，大概就是这个样子，所以直接暴力枚举i判断gcd是否等于1就可以了。