2820:YYのGCD|莫比烏斯は反演します。
1389 ワード
http://blog.csdn.net/acdreamers/article/details/8542292
こんなに神の問題はどうしてできますか?
こんなに神の問題はどうしてできますか?
#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define T 10000005
using namespace std;
int sc()
{
int i=0; char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
return i;
}
int sum[T],mu[T]={0,1},a[T],prime[T/10];
int top;
void Pretreatment()
{
for(int i=2;i<T;i++)
{
if(!a[i])
{
prime[++top]=i;
mu[i]=-1;
}
for(int j=1;j<=top&&prime[j]*i<T;j++)
{
a[prime[j]*i]=1;
if(i%prime[j]==0)
break;
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=top;i++)
{
for(int j=prime[i];j<T;j+=prime[i])
{
sum[j]+=mu[j/prime[i]];
}
}
for(int i=1;i<T;i++)sum[i]+=sum[i-1];
}
long long cal(int x,int y)
{
long long ans=0;
for(int i=1,last;i<=x&&i<=y;i=last+1)
{
last=min(x/(x/i),y/(y/i));
ans+=(long long)(sum[last]-sum[i-1])*(x/i)*(y/i);
}
return ans;
}
int main()
{
Pretreatment();
for(int n=sc();n;n--)
{
int x=sc(),y=sc();
printf("%lld
",cal(x,y));
}
return 0;
}