题意：
其中N的范围1e7
题解：
如果是对于确定的素数p，求
那么显然是莫比乌斯反演入门题，预处理莫比乌斯函数后，可以通过数论分块优化到求解答案。
而本题中所求为
即为
我们已经知道内层可以通过数论分块来优化了。
但是这个复杂度估计仍然是过不了的，我们需要进一步优化。
既然我们会用数论分块，那么应该会比较敏感的发现，对于内层求和符号上的，同样可以通过数论分块来进行优化，这样最后的时间复杂度近似于。
（:经qko提醒，双重数论分块的时间复杂度为???????
具体的做法：
先线性筛预处理莫比乌斯函数前缀和，同时也会打出素数表。观察到N为1e7也只有不超过7e5个素数，素数表数组可以只开到7e5；同时观察到莫比乌斯函数前缀和中最大值为1143，最小值为-1078，节省空间，可以开成short型的数组。
预处理后，计算答案时，对外层的素数表分块时，可通过二分查找来找到使得的r。
对于同一块内，通过数论分块计算内层的ans1，然后当前块的答案就是ans1*(r-l+1)。
那么总的答案就是所有块答案之和。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e7+5;
const int MAXM=7e5;
bool notprime[MAXN];
int prime[MAXM],cnt;
short mu[MAXN];//max:1143
void init(int n){mu[1]=notprime[1]=1;for(int i=2;i<=n;i++){if(!notprime[i]) prime[cnt++]=i,mu[i]=-1;for(int j=0;j<cnt&&prime[j]*i<=n;j++){notprime[i*prime[j]]=1;if(i%prime[j]==0) break;mu[i*prime[j]]=-mu[i];}}for(int i=1;i<=n;i++) mu[i]+=mu[i-1];
}
int main(){int n;cin>>n;init(n);ll ans=0,ans1;for(int l=0,r,tt;l<cnt;l=r+1){tt=n/prime[l];r=upper_bound(prime,prime+cnt,n/tt)-prime-1;ans1=0;for(int l1=1,r1,tt1;l1<=tt;l1=r1+1){tt1=tt/l1;r1=tt/tt1;ans1+=(mu[r1]-mu[l1-1])*1ll*tt1*tt1;}ans+=(r-l+1)*ans1;}cout<<ans<<"\n";return 0;
}