最终得对抗自己

Tags » 杜教筛

[51Nod 1238]最小公倍数之和 V3 杜教筛

世界之大,无奇不有。
如何突破线性筛法的极限速度?
用低于线性的复杂度求得积性函数前缀和。

给定N,求
$$ \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{gcd(i,j)} $$
N<=10^10,答案对10^9+7取模。

这题并不简单。