题意 【数论|HDU 6706 huntian oy(杜教筛)】给你n计算函数
f ( n , a , b ) = ∑ i = 1 n ∑ j = 1 i g c d ( i a ? j a , i b ? j b ) [ g c d ( i , j ) = = 1 ] m o d     1 e 9 + 7 f(n,a,b)=\sum_{i=1}^{n}\sum_{j=1}^igcd(i^a-j^a,i^b-j^b)[gcd(i,j)==1]\mod 1e^9+7 f(n,a,b)=i=1∑n?j=1∑i?gcd(ia?ja,ib?jb)[gcd(i,j)==1]mod1e9+7
思路 数论中的若干定理，也可以通过打表发现
若 n > m n> m n>m, g c d ( n , m ) = 1 gcd(n,m)=1 gcd(n,m)=1,那么 g c d ( n a ? m a , n b ? m b ) = n g c d ( a , b ) ? m g c d ( a , b ) gcd(n^a-m^a,n^b-m^b)=n^{gcd(a,b)}-m^{gcd(a,b)} gcd(na?ma,nb?mb)=ngcd(a,b)?mgcd(a,b)
那又有题目中说了 a a a与 b b b互质，那么原式就转变为
∑ i = 1 n ∑ j = 1 i i ? j [ g c d ( i , j ) = = 1 ] \sum_{i=1}^n\sum_{j=1}^ii-j[gcd(i,j)==1] i=1∑n?j=1∑i?i?j[gcd(i,j)==1]
我们先只考虑后面这个式子
∑ j = 1 i i ? j [ g c d ( i , j ) = = 1 ] \sum_{j=1}^ii-j[gcd(i,j)==1] j=1∑i?i?j[gcd(i,j)==1]
这个式子的含义就是 1 1 1到 i i i中与 i i i互质的数与 i i i的差的和。我们也知道 1 1 1到 n ( n > 1 ) n(n> 1) n(n>1)中与 n n n互质的数的和为 n φ ( n ) 2 \frac{n\varphi(n)}{2} 2nφ(n)?,与 n n n互质的数的个数就是 φ ( n ) \varphi(n) φ(n)。那么式子就为
∑ j = 1 i i ? j [ g c d ( i , j ) = = 1 ] = i φ ( i ) ? i φ ( i ) 2 ( i > 1 ) \sum_{j=1}^ii-j[gcd(i,j)==1]=i\varphi(i)-\frac{i\varphi(i)}{2}(i> 1) j=1∑i?i?j[gcd(i,j)==1]=iφ(i)?2iφ(i)?(i>1)
原式就等于 ( i = 1 ) (i=1) (i=1)答案为 0 0 0没有贡献
∑ i = 2 n i φ ( i ) ? i φ ( i ) 2 = ∑ i = 2 n i φ ( i ) 2 \sum_{i=2}^ni\varphi(i)-\frac{i\varphi(i)}{2}=\sum_{i=2}^n\frac{i\varphi(i)}{2} i=2∑n?iφ(i)?2iφ(i)?=i=2∑n?2iφ(i)?
对这个式子我们可以换成求解
∑ i = 1 n i φ ( i ) \sum_{i=1}^ni\varphi(i) i=1∑n?iφ(i)
用狄利克雷卷积求杜教筛的方法，对于原函数 ∑ i = 1 n i ? φ ( i ) \sum_{i=1}^ni*\varphi(i) ∑i=1n?i?φ(i)
令 f ( x ) = x φ ( x ) f(x)=x\varphi(x) f(x)=xφ(x)，考虑这个函数卷上一个什么函数求前缀和会比较容易呢
已知 ( φ ? I ) ( n ) = i d (\varphi*I)(n)=id (φ?I)(n)=id，
有一个小技巧就是把卷上一个函数能把前面的系数给消掉变为常数的，那么我们再卷上一个 x x x就可以了
令 g ( x ) = x g(x)=x g(x)=x
那么

∑ d ∣ n g ( d ) f ( n d ) = ∑ d ∣ n d n d φ ( n d ) = n ∑ d ∣ n φ ( n d ) = n 2 \sum_{d|n}g(d)f(\frac{n}{d})=\sum_{d|n}d\frac{n}{d}\varphi(\frac{n}{d})=n\sum_{d|n}\varphi(\frac{n}{d})=n^2 d∣n∑?g(d)f(dn?)=d∣n∑?ddn?φ(dn?)=nd∣n∑?φ(dn?)=n2
所以这两个函数的卷积的前缀和是很好求的
令 S ( n ) = ∑ i = 1 n f ( i ) S(n)=\sum_{i=1}^nf(i) S(n)=∑i=1n?f(i)有

∑ i = 1 n g ? f = ∑ i = 1 n ∑ d ∣ i g ( d ) f ( i d ) = ∑ i = 1 n i 2 \sum_{i=1}^ng*f=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})=\sum_{i=1}^ni^2 i=1∑n?g?f=i=1∑n?d∣i∑?g(d)f(di?)=i=1∑n?i2
∑ i = 1 n ∑ d ∣ i g ( d ) f ( i d ) \sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d}) i=1∑n?d∣i∑?g(d)f(di?)
对于这个式子是枚举1到n中每个数的因子的，他和枚举1到n中每个数的倍数是等价的那就有
∑ i = 1 n ∑ d ∣ i g ( d ) f ( i d ) = ∑ d = 1 n ∑ i = 1 ? n d ? g ( d ) f ( i ) = ∑ d = 1 n g ( d ) ∑ i = 1 ? n d ? f ( i ) = ∑ d = 1 n g ( d ) S ( ? n d ? ) \sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})=\sum_{d=1}^n\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}g(d)f(i)=\sum_{d=1}^ng(d)\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}f(i)=\sum_{d=1}^ng(d)S(\left \lfloor \frac{n}{d} \right \rfloor) i=1∑n?d∣i∑?g(d)f(di?)=d=1∑n?i=1∑?dn???g(d)f(i)=d=1∑n?g(d)i=1∑?dn???f(i)=d=1∑n?g(d)S(?dn??)
∑ d = 1 n g ( d ) S ( ? n d ? ) = g ( 1 ) S ( n ) + ∑ d = 2 n g ( d ) S ( ? n d ? ) = ∑ i = 1 n i 2 \sum_{d=1}^ng(d)S(\left \lfloor \frac{n}{d} \right \rfloor)=g(1)S(n)+\sum_{d=2}^ng(d)S(\left \lfloor \frac{n}{d} \right \rfloor)=\sum_{i=1}^ni^2 d=1∑n?g(d)S(?dn??)=g(1)S(n)+d=2∑n?g(d)S(?dn??)=i=1∑n?i2
g ( 1 ) S ( n ) = ∑ i = 1 n i 2 ? ∑ d = 2 n g ( d ) S ( ? n d ? ) g(1)S(n)=\sum_{i=1}^ni^2-\sum_{d=2}^ng(d)S(\left \lfloor \frac{n}{d} \right \rfloor) g(1)S(n)=i=1∑n?i2?d=2∑n?g(d)S(?dn??)
由于 g ( x ) = x g(x)=x g(x)=x，所以
S ( n ) = n ( n + 1 ) ( 2 n + 1 ) 6 ? ∑ d = 2 n d S ( ? n d ? ) S(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{d=2}^ndS(\left \lfloor \frac{n}{d} \right \rfloor) S(n)=6n(n+1)(2n+1)??d=2∑n?dS(?dn??)
套杜教筛就可以了
求完 S ( n ) S(n) S(n)后，那么答案就是
S ( n ) ? 1 2 \frac{S(n)-1}{2} 2S(n)?1?
把多出来的一个 1 1 1减掉就是 ∑ i = 2 n i φ ( i ) \sum_{i=2}^n i\varphi(i) i=2∑n?iφ(i)
除以二就是答案了

#include using namespace std; const int N=1e6+5; const int mod=1e9+7; const int inv6=166666668; const int inv2=500000004; long long phi[N]; bool vis[N]; int prime[N]; int cnt; void init() { phi[1]=1; cnt=0; for(int i=2; iP; long long S(long long n) { if(n