HoshiuZ

分类

题解(1)

/ 注册

全部文章（共1篇）

GCD

链接 GCD 思路显然，除了素数的整数次幂，其余的数的值均为。对于一个素数，则有。于是可以考虑在线性筛素数的过程中预处理出，这很好预处理，线性筛中记录下每个数的最小质因数 ,然后对有大于一个质因子的数打上标记。时间复杂度为。代码 #include<bits/s...

2020-10-21

3 645