http://hzwer.com/6142.html 额……. 题解就抄hzwer的把……….. 还有，对于公式是怎么推出来的，慢慢推就好了； 然后是下底分段，我竟然字节写出来了； 其实洛谷上对于下底分段我也做过，也是直接做的； http://blog.csdn.net/largecub233/article/details/65628216 这个也是下底分段
#include<iostream> #include<cstdio> #include<algorithm> #include<map> #define pa pair<int,int> #define Ll long long using namespace std; const int N=1e7+5; int u[N],pri[N],tot; bool com[N]; Ll f[N]; int t,n,m; Ll ans; void mobius(){ u[1]=1; for(int i=2;i<=N;i++){ if(!com[i]){pri[++tot]=i;u[i]=-1;} for(int j=1;j<=tot&&pri[j]*i<=N;j++){ com[pri[j]*i]=1; if(i%pri[j])u[pri[j]*i]=-u[i];else { u[pri[j]*i]=0; break; }}}} void make(){ for(int i=1;i<=tot;i++) for(int j=pri[i];j<=N;j+=pri[i])f[j]+=u[j/pri[i]]; for(int i=1;i<=N;i++)f[i]+=f[i-1]; } int main() { mobius(); make(); scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); if(n>m)swap(n,m); for(int k=1;k<=n;){ int kk=min(n/(n/k),m/(m/k)); ans+=(f[kk]-f[k-1])*(n/k)*(m/k); k=kk+1; } printf("%lld\n",ans);ans=0; } }