"2018 南京网络预赛"Sum - 线性筛
定义 为满足以下条件的有序二元组 的方案数(即 与 被认为是不同的方案):
和 均为无平方因子数(即其因子中没有除 以外的完全平方数).
求 ,.
计蒜客 30999
显然, 是积性函数,考虑线性筛.
当 为素数时,,即 与 ;
当 的最小质因子为 ,且 时,;
如果 ,那么 中 的指数至少为 ,即无论如何划分 ,两个数中一定有一个数中 的指数为 ,即不存在合法的划分方案.
否则, 中 的指数至少为 ,把这两个 分别分给 中的 和 ,剩余的 就是一个子问题了,即 .
// #include <vector>
const int MAXN = 2e7;
bool isNot