2018-07-15 20:50:49

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$$

$$=\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\ \ \ (k\in prime)$$

$$=\sum_{k=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]\ \ \ (k\in prime)$$

$$\sum_{d|n}\mu(d)=[n=1]$$

$$[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)$$

$$=\sum_{k=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)\ \ \ (k\in prime)$$

$$=\sum_{k=1}^{n}\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*\lfloor\frac{n}{kd}\rfloor*\lfloor\frac{m}{kd}\rfloor\ \ \ (k\in prime)$$

$$=\sum_{k=1}^{n}\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\ \ \ (k\in prime)$$

$$=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\sum_{k|T,k\in pimre}\mu(\frac{T}{k})$$

void sieve() {
mu[1]=1;
for (int i=2;i<=10000000;i++) {
if (!flag[i]) prime[++cnt]=i,mu[i]=-1;
for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
flag[i*prime[j]]=1;
if (i%prime[j]==0) break;
mu[i*prime[j]]=-mu[i];
}
}
for (int i=1;i<=cnt;i++)
for (int j=1;prime[i]*j<=10000000;j++)
f[j*prime[i]]+=mu[j];
for (int i=1;i<=10000000;i++)
sum[i]=sum[i-1]+f[i];
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL mu[10000010];int flag[10000010],prime[10000010],cnt,f[10000010],sum[10000010];
void sieve() {
mu[1]=1;
for (int i=2;i<=10000000;i++) {
if (!flag[i]) prime[++cnt]=i,mu[i]=-1;
for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
flag[i*prime[j]]=1;
if (i%prime[j]==0) break;
mu[i*prime[j]]=-mu[i];
}
}
for (int i=1;i<=cnt;i++)
for (int j=1;prime[i]*j<=10000000;j++)
f[j*prime[i]]+=mu[j];
for (int i=1;i<=10000000;i++)
sum[i]=sum[i-1]+f[i];
}
LL solve(int a,int b) {
LL ans=0;
if (a>b) swap(a,b);
for (int l=1,r=0;l<=a;l=r+1) {
r=min(a/(a/l),b/(b/l));
ans+=(LL)(sum[r]-sum[l-1])*(LL)(a/l)*(LL)(b/l);
}
return ans;
}
int main() {
sieve();
int n,m,T;scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&m);
if (n>m) swap(n,m);
printf("%lld\n",solve(n,m));
}
}
• star
首页