题目：
HDU---6706：huntian oy
题意:
给定N，a，b，求下面式子的值（求和后再mod 1e9+7）：
文章图片
分析：
一直怯于杜教筛不敢去学习【一看就会的杜教筛】，今天终于迈出了这一步，才发现并没有那么难（哈哈哈）
首先有：gcd(i^a-j^a,i^b-j^b) = i^(gcd(a,b))-j^(gcd(a,b)) = i - j（a，b互质），熟悉欧拉函数就容易转化为：
文章图片
文章图片
文章图片
那么就要快速求得i*phi[i]的前缀和即可，显然 f(i) = i*phi[i] 这是个积性函数，那就可以套用杜教筛来求，设积性函数h，g，满足：h = f*g，将其表示成狄利克雷卷积形式：
【比赛----题解|2019年CCPC - 网络赛E（huntian oy【杜教筛】）】
文章图片
那么令g函数等于单位函数id，即可求得h(n) = (f*g)(n) = n^2，令S(n)表示f函数的前缀和，则有：
文章图片
前面求和用平方求和公式O(1)求的，后面整除分块+递归求的即可
代码：
#include using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int maxn = 5e6+205;
const int inv2 = 500000004;
const int inv6 = 166666668;
map mp;
int prime[maxn],phi[maxn],cnt;
void init(){
phi[1] = 1;
for(int i = 2;
i < maxn;
++i){
if(!phi[i]) phi[i]=i-1,prime[cnt++]=i;
for(int j = 0;
j= mod) phi[i] -= mod;
}
}
int solve(int n){
if(n < maxn) return phi[n];
if(mp.count(n)) return mp[n];
int res = 0;
for(int d=2,last;
d<=n;
d=last+1){
int tep = n/d;
last = n/tep;
res += 1ll*(last+d)*(last-d+1)%mod*inv2%mod*solve(tep)%mod;
if(res >= mod) res -= mod;
}
return mp[n] = (1ll*n*(n+1)%mod*(2*n+1)%mod*inv6%mod-res+mod)%mod;
}
int main(){
int T,n,a,b;
init();
scanf("%d",&T);
while(T--){
scanf("%d %d %d",&n,&a,&b);
printf("%d\n",(int)(1ll*inv2*(solve(n)-1+mod)%mod));
}
return 0;
} 
