这道题是欧拉函数的使用，这里简要介绍下欧拉函数。
欧拉函数定义为：对于正整数n,欧拉函数是指不超过n且与n互质的正整数的个数。
欧拉函数的性质：1.设n = p1a1p2a2p3a3p4a4...pkak为正整数n的素数幂分解，那么φ(n) = n·(1-1/p1)·(1-1/p2)·(1-1/p3)···(1-1/pk)
2.如果n是质数，则φ(n) = n-1; 反之，如果p是一个正整数且满足φ(p)=p-1，那么p是素数。
3.设n是一个大于2 的正整数，则φ(n)是偶数
4.当n为奇数时，有φ(2n)=φ(n)
5.设m和n是互质的正整数，那么φ(mn)=φ(m)φ(n)
（1）可以根据性质1，写出计算欧拉函数值的程序： 复杂度为O(√n)
//直接求解欧拉函数
int euler(int n){ //返回euler(n)
int res=n;
for(int i=;i*i<=n;i++){
if(n%i==){
res=res/i*(i-);//先进行除法是为了防止中间数据的溢出
while(n%i==) n/=i;
}
}
if(n>) res=res/n*(n-);
return res;
}
（2）上面这种写法中，在for循环中选择i时，是顺序选择的。事实上性质1 中的p1、p2、p3、p4、...pk都是质数。如果在选择时，直接选择质数进行判断，那结果会优化很多。
可以先把50000以内的素数用筛法选出来并保存，以方便欧拉函数使用。这样，在不考虑筛法的时间复杂度，而单看欧拉函数，其复杂度变为O(x),x为√n以内素数的个数。
#include <cstring>
bool boo[];int p[]; void prim(){
//线性筛素数
memset(boo,,sizeof(boo));
boo[]=boo[]=;
int k=;
for(int i=;i<;i++){
if(!boo[i]) p[k++]=i;
for(int j=;j<k&&i*p[j]<;j++){
boo[i*p[j]] = ;
count++;
if(!(i%p[j])) break;
}
} } int phi(int n){
int rea = n;
for(int i=;p[i]*p[i]<=n;i++ ){ //对一些不是素数的可不用遍历
if(n%p[i]==){
rea = rea-rea/p[i];
while(n%p[i]==) n/=p[i];
}
}
if(n>) rea-=rea/n;
return rea;
}
（3）递推求欧拉函数
如果频繁的要使用欧拉函数值，就需要预先打表。复杂度约为O(nlnn)
//递推法打欧拉函数表
#define Max 1000001
int phi[Max];
void Init(){
for(int i=;i<=Max;i++) phi[i]=i;
for(int i=;i<=Max;i+=) phi[i]/=;
for(int i=;i<=Max;i+=)
if(phi[i]==i)
for(int j=i;j<=Max;j+=i)
phi[j]=phi[j]/i*(i-);//先进行除法是为了防止中间数据的溢出
}
应用：NYOJ 998 http://acm.nyist.net/JudgeOnline/problem.php?pid=998
这道题的精华如何将符合条件的gcd(x,n)表达出来：见代码 d*Euler(n/d) 中为什么乘以d的解释 。
然后是遍历一遍小于n的数，测试每个符合的数加起来即可。其实还可以更快，观察发现，在能够整除n的i里面，相对应的n/i也有相似的性质，这样以来只需要遍历到sqrt(n)即可。
网络摘抄代码如下：
#include<iostream>
#include<cstdio>
using namespace std; 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;
} int main(){
LL n,m;
while(cin>>n>>m){
LL ans = ;
for(int i = ; i * i <= n; i++){
if(n % i == ){
if(i >= m){
int d = i;
ans += d*Euler(n/d);
// 考虑 gcd(x,n) 1=<x<=n
//这个的由来是 gcd(x/d,n/d) = 1.如果我们取一个能让n/d取整数的d的取值，于是我们
//取到了n%i==0的i,于是 能够满足gcd(x,n) = d 的x的个数为Euler(n/d)个
//那么在该gcd = d 的情况下需要加到ans里面的d的个数就是Euler(n/d)个 ，所以有ans+=d*Euler(n/d) }
if(i * i != n && n / i >= m){
int d = n / i;
ans += d*Euler(n/d);
}
}
}
cout<<ans<<endl;
}
return ;
}