记录编号	413673	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2820] YY的GCD	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	8.976 s
提交时间	2017-06-11 21:58:47	内存使用	238.81 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 10000005;
typedef long long LL;
int mu[MAXN],prime[MAXN];
LL sum[MAXN],f[MAXN];
int n[10005],m[10005],maxn,cnt;
bool _prime[MAXN];


void get(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!_prime[i]){
            mu[i]=-1;
            prime[++cnt]=i;
            f[i]=1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            _prime[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                f[i*prime[j]]=mu[i];
                break;
            }
            mu[i*prime[j]]=-mu[i];
            f[i*prime[j]]=mu[i]-f[i];
        }
    }

    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+f[i];

}

void calc(int T){
    int N=n[T],M=m[T];
    if(N>M)swap(N,M);
    int last;
    LL ans=0;
    for(int i=1;i<=N;i=last+1){
        last=min(N/(N/i),M/(M/i));
        ans=ans+(sum[last]-sum[i-1])*(N/i)*(M/i);
    }
    printf("%lld\n",ans);
}


int main(){

    freopen("YYnoGCD.in","r",stdin);

    freopen("YYnoGCD.out","w",stdout);

    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)scanf("%d%d",&n[i],&m[i]),maxn=max(maxn,max(n[i],m[i]));
    get(maxn);
    for(int i=1;i<=t;i++)calc(i);
}