在博客NYOJ 998 中已经写过计算欧拉函数的三种方法，这里不再赘述。
本题也是对欧拉函数的应用的考查，不过考查了另外一个数论基本定理：如何用欧拉函数求小于n且与n互质所有的正整数的和。
记euler(x)公式能计算小于等于x的并且和x互质的数的个数；我们再看一下如何求小于等于n的和n互质的数的和， 我们用sum(n)表示；
定理：若gcd(x, a)=1，则有gcd(x, x-a)=1；
证明：反证法：假设gcd(x, x-a)=k (k>1)，那么有(x-a)%k=0---1式，x%k=0---2式； 由1式和2式可得 a%k=0---3式； 由2式和3式可得gcd(x, a)=k，与gcd(x,a)=1矛盾，假设不成立，即原式得证；
由此我们可以得知小于x并且与x互质的数必然是成对出现的并且有对应的一对数和为x；所以有sum(n)=euler(n)/2*n；
故本题的写法为：
#include <iostream>
#include <cstdio>
using namespace std; const int N= ;
typedef long long LL; LL Euler(LL n){
LL ans = n;
for(int i = ; i * i <= n; i++){
if(n % i == ){
ans = ans / i * (i-);
while(n % i == )
n /= i;
}
}
if(n > ) ans = ans / n * (n-);
return ans;
} //计算得到小于n且与n互质的正整数的和
long long Euler_sum(long long n){
if(n==)
return ;
else
return n*Euler(n)/;
} int main(){
int t;
cin>>t;
while(t--){
LL n,m;
cin>>n>>m;
LL ans = ;
for(int i = ; i * i <= n; i++){
if(n % i == ){
if(i >= m){
int d = i;
ans = (ans+d*Euler_sum(n/d) ) %N;
//考虑gcd(x,n) 1<=x<=n
//其中gcd(x/d,n/d) = 1 ,Euler(n/d)我们得到的是能够使得gcd(x,n) = d 的x的取值的个数
//Euler_sum(n/d)我们得到的是小于n/d且与n/d互质的正整数的和
//暂且设“小于n/d且与n/d互质的正整数”分别为a1,a2...an等那么乘以d之后得到的数列b1 = a1*d b2 = a2*d ...bn = an*d
//那么b1 b2 ...bn等数与n的公约数就是d ,而d>=m,满足题设
//所以在公约数为d的情况下这些能够满足gcd(x,n) = d >=m的数的和，即b1+b2+...bn = (a1+a2+...+an)*d,
//而(a1+a2+...+an) = Euler_sum(n/d) 故b1+b2+...bn = d*Euler_sum(n/d)
//这样就处理完了公约数为d的情况，同理按照for循环，1~sqrt(n)遍历，
//分别测试公约数为别等于i（i从1到sqrt(n)遍历）是否满足n%i==0即可，若满足就令d=i,ans+=d*Euler_sum(n/d)
}
if(i * i != n && n / i >= m){
int d = n / i;
ans = (ans+ d*Euler_sum(n/d) )%N;
//在上部for循环中进行到sqrt(n),这一步就是处理后面的东西：n/i
}
}
}
cout<<ans<<endl;
}
return ;
}