【HDU 6704 huntian oy 杜教筛】注意到 a , b a,b a,b互质，而 g c d ( i a ? j a , i b ? j b ) = i g c d ( a , b ) ? j g c d ( a , b ) = i ? j gcd(i^a-j^a,i^b-j^b)=i^{gcd(a,b)}-j^{gcd(a,b)}=i-j gcd(ia?ja,ib?jb)=igcd(a,b)?jgcd(a,b)=i?j
前面的一部分其实就是 i ? j i-j i?j。然后只要拆开就容易注意到：
∑ i = 1 n i ∑ j = 1 i [ g c d ( i , j ) = 1 ] = ∑ i = 1 n i ? ( i ) \sum_{i=1}^{n}i\sum_{j=1}^{i}[gcd(i,j)=1]=\sum_{i=1}^{n}i\phi(i) ∑i=1n?i∑j=1i?[gcd(i,j)=1]=∑i=1n?i?(i)。
∑ i = 1 n ∑ j = 1 i j [ g c d ( i , j ) = 1 ] = ∑ i = 1 n i ? ( i ) + [ n = 1 ] 2 \sum_{i=1}^{n}\sum_{j=1}^{i}j[gcd(i,j)=1]=\sum_{i=1}^{n}\frac{i\phi(i)+[n=1]}{2} ∑i=1n?∑j=1i?j[gcd(i,j)=1]=∑i=1n?2i?(i)+[n=1]?
前者是欧拉函数的定义，后者是互质数的和，这是个经典问题。
最后要求的就是 ∑ i = 1 n i ? ( i ) ? 1 2 \sum_{i=1}^{n}\frac{i\phi(i)-1}{2} ∑i=1n?2i?(i)?1?。
n ≤ 1 e 9 n\le1e9 n≤1e9，考虑用杜教筛求 i ? ( i ) i\phi(i) i?(i)的前缀和，而 i ? ? i d = n 2 i\phi*id=n^2 i??id=n2，记 i ? ( i ) i\phi(i) i?(i)的前缀和为 S ( i ) S(i) S(i)，可以得到 S ( n ) = ∑ i = 1 n i 2 ? ∑ d = 2 n d S ( n d ) S(n)=\sum_{i=1}^{n}i^2-\sum_{d=2}^{n}dS(\frac{n}{d}) S(n)=∑i=1n?i2?∑d=2n?dS(dn?)，前面的直接通项公式 O ( 1 ) O(1) O(1)，后面的一部分数论分块+ O ( 1 ) O(1) O(1)处理 d d d，先用线性筛筛出 1 e 6 1e6 1e6以内的 p h i phi phi，总复杂度是 O ( n 2 3 ) O(n^\frac{2}{3}) O(n32?)。
#include
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=LONG_LONG_MAX;
const int N=2e6+7;
const int mod=1e9+7;
int pri[N],phi[N],sum[N];
bool ok[N];
unordered_map mp;
void getphi() {
int tot=0;
phi[1]=1;
for(int i=2;
i 
