分析（官方题解）：
一点感想：
首先上面那个等式成立，然后就是求枚举gcd算贡献就好了，枚举gcd当时赛场上写了一发O(nlogn)的反演，写完过了样例，想交发现结束了
吐槽自己手速慢，但是发了题解后发现，这题连O(n)欧拉函数前缀和的都卡了，幸亏没交，还是太年轻
对于官方题解说sqrt(n)优化（其实就是n/（小于n一段数）结果是一样的，也不算什么分块），还是很简单的，做反演题的时候看到过很多，只是忘记了
如果不会请看这篇解题报告http://wenku.baidu.com/view/fbe263d384254b35eefd34eb.html
细节处理：注意特判x=1的情况，然后处理(x-1)的逆元，等比数列求和需要用，感觉这题还是能做出来的
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+;
const LL mod = 1e9+;
int phi[N],T;
LL sum[N],x,n;
LL qpow(LL a,LL b){
LL ret=;
while(b){
if(b&)ret=(ret*a)%mod;
b>>=;
a=(a*a)%mod;
}
return ret;
}
inline void up(LL &x,LL y){
x+=y;if(x>=mod)x-=mod;
}
int main(){
phi[]=;
for(int i=;i<=N-;++i)if(!phi[i]){
for(int j=i;j<=N-;j+=i){
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
for(int i=;i<=N-;++i)sum[i]=sum[i-]+1ll*phi[i];
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d",&x,&n);
if(x==){
printf("0\n");continue;
}
LL inv=qpow(x-,mod-),ret=;
for(int i=,j;i<=n;i=j+){
j=n/(n/i);
LL a0=qpow(x,i),qn=qpow(x,j-i+);
up(qn,mod-);
a0=a0*qn%mod*inv%mod;
up(a0,mod-(j-i+));
a0=(2ll*sum[n/i]-)%mod*a0%mod;
up(ret,a0);
}
printf("%I64d\n",ret);
}
return ;
}