给会玩线性筛的大爷跪了。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 10000050 using namespace std; int t,n,m,prime[maxn/10],tot=0,mn[maxn],last[maxn],g[maxn],cnt[maxn]; bool vis[maxn]; int judge(int x) { if (x&1) return -1; return 1; } void get_table() { mn[1]=last[1]=0; for (int i=2;i<=maxn;i++) { if (!vis[i]) { mn[i]=1;last[i]=0;g[i]=1;cnt[i]=1; prime[++tot]=i; } for (int j=1;j<=tot && i*prime[j]<=maxn-50;j++) { vis[i*prime[j]]=true; if (i%prime[j]) { cnt[i*prime[j]]=cnt[i]+1; if ((last[i]!=mn[i]) && (last[i])) last[i*prime[j]]=-1;else last[i*prime[j]]=mn[i]; mn[i*prime[j]]=1; if ((mn[i*prime[j]]==last[i*prime[j]]) || (!last[i*prime[j]])) g[i*prime[j]]=judge(cnt[i*prime[j]]+1);else g[i*prime[j]]=0; continue; } cnt[i*prime[j]]=cnt[i];mn[i*prime[j]]=mn[i]+1;last[i*prime[j]]=last[i]; if ((mn[i*prime[j]]==last[i*prime[j]]) || (!last[i*prime[j]])) g[i*prime[j]]=judge(cnt[i*prime[j]]+1);else g[i*prime[j]]=0; } } for (int i=1;i<=maxn-50;i++) g[i]+=g[i-1]; } int main() { scanf("%d",&t);get_table(); for (int i=1;i<=t;i++) { scanf("%d%d",&n,&m); if (n>m) swap(n,m); int l=1,r;long long ans=0; while (l<=n) { r=min(n/(n/l),m/(m/l)); ans+=(long long)(n/l)*(m/l)*(g[r]-g[l-1]); l=r+1; } printf("%lld ",ans); } return 0; }