[文章目录]
Description
就是求一个p为质数。多组输入<= n,m<=
考虑犹如[gcd(i,j)==1]一样化简；=> (p为质数)
又因为
=>(p为质数)
考虑每个被累加的次数=>
我们发现右面次数可以求出，考虑左边。只需要求出来一个前缀和就好了。不妨设T=p*d.那么只需要求出来
%%%EdwardFrog,暴力枚举质数更新答案(据说均摊复杂度大概是O(n)的)。
不考虑这种玄学算法，我们快筛。设这个函数为f(T)
如果i%pri==0:f(i*pri)中，我们发现当中p不为pri的时候，都为0，当p为pri的时候才有可能不为0，才能够对答案有贡献.那么答案就是：
第一个公式：if(i%pri==0) f(i*pri)=
考虑另一种情况：i%pri!=0，我们发现中当p不为pri的时候，T都相当于多乘了个pri。那么，所有的都相当于乘上一个-1.当p为pri的时候，这个东西等于
第二个公式：else f(i*pri)=-f(i)+
快筛吧。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 10000000
int T,n,m,cnt;
int mu[10001000],pri[701000];
int sum[10001000];
bool v[10001000];
void initialize()
{
mu[1]=1;
for(int i=2;i<=N;i++)
{
if(!v[i]) pri[++cnt]=i,mu[i]=-1,sum[i]=1;
for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
{
v[i*pri[j]]=1;
if(i%pri[j]==0)
{
mu[i*pri[j]]=0;
sum[i*pri[j]]=mu[i];
break;
}
else
{
mu[i*pri[j]]=mu[i]*-1;
sum[i*pri[j]]=-sum[i]+mu[i];
}
}
}
for(int i=1;i<=N;i++)
sum[i]+=sum[i-1];
}
ll query(int x,int y)
{
if(x>y) swap(x,y);
int b=1,e;
ll re=0;
while(b<=x)
{
e=min(x,min(x/(x/b),y/(y/b)));
re+=1ll*(sum[e]-sum[b-1])*(x/b)*(y/b);
b=e+1;
}
return re;
}
int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int main()
{
initialize();
scanf("%d",&T);
while(T--)
{
n=read(); m=read();
printf("%lld\n",query(n,m));
}
return 0;
}