题解参考syh学长的博客：http://www.cnblogs.com/AOQNRMGYXLMV/p/4932537.html %%%
关于这一类求积性函数前缀和的方法，学习参考博客：http://blog.csdn.net/skywalkert/article/details/50500009
要好好看大神的博客哦orz
用筛法预处理前N^(2/3)项，后面的记忆化搜索解决。
不太会用哈希，就用map记忆化一下：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define CLR(a,b) memset((a),(b),sizeof((a)))
typedef long long ll;
const int N = ;
bool check[N+];
int prime[N+];
int mu[N+];
ll mu_sum[N+];
void Moblus(){
CLR(check, false);
mu[] = ;
int tot = ;
for(int i = ; i <= N; i++){
if( !check[i] ){
prime[tot++] = i;
mu[i] = -;
}
for(int j = ; j < tot && i*prime[j] <= N; j++){
check[i * prime[j]] = true;
if( i % prime[j] == ){
mu[i * prime[j]] = ;
break;
}
else
mu[i * prime[j]] = -mu[i];
}
}
for(int i = ; i <= N; ++i)
mu_sum[i] = mu_sum[i-] + mu[i];
}
map<ll,ll> mp;
ll Mertens(ll n){
if(n <= N) return mu_sum[n];
if(mp.count(n)) return mp[n];
ll ans = , ed;
for(ll i = ; i <= n; i = ed+){
ed = n/(n/i);
ans -= (ed - i + )*Mertens(n/i);
}
return mp[n] = ans;
}
int main(){
Moblus();
ll a, b;
scanf("%lld%lld", &a, &b);
printf("%lld\n", Mertens(b) - Mertens(a-));
return ;
}