简单题

题意:

求:
∑ i = 1 n ∑ j = 1 m g c d ( i , j ) φ ( i j ) μ ( i j ) \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\varphi(ij)\mu(ij) i=1nj=1mgcd(i,j)φ(ij)μ(ij)
多组数据。
为了减小输出大小,你只需输出上式模 2 32 2^{32} 232的值

Solution:

首先知道一些函数的特点:
φ ( i j ) = φ ( i ) φ ( j ) g c d ( i , j ) φ ( g c d ( i , j ) ) μ ( i j ) = μ ( i ) μ ( j ) [ g c d ( i , j ) = 1 ] \varphi(ij)=\frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))} \\ \mu(ij)=\mu(i)\mu(j)[gcd(i,j)=1] φ(ij)=φ(gcd(i,j))φ(i)φ(j)gcd(i,j)μ(ij)=μ(i)μ(j)[gcd(i,j)=1]
那么
∑ i = 1 n ∑ j = 1 m g c d ( i , j ) φ ( i j ) μ ( i j ) = ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) φ ( i ) φ ( j ) g c d ( i , j ) φ ( g c d ( i , j ) ) μ ( i j ) = ∑ i = 1 n ∑ j = 1 m φ ( i ) φ ( j ) g c d ( i , j ) 2 φ ( g c d ( i , j ) ) μ ( i j ) = ∑ i = 1 n ∑ j = 1 m φ ( i ) φ ( j ) [ g c d ( i , j ) = 1 ] μ ( i ) μ ( j ) = ∑ i = 1 n ∑ j = 1 m ∑ d ∣ g c d ( i , j ) μ ( d ) φ ( i ) φ ( j ) μ ( i ) μ ( j ) = ∑ d = 1 m i n ( n , m ) μ ( d ) ∑ d ∣ i n φ ( i ) μ ( i ) ∑ d ∣ j m φ ( j ) μ ( j ) \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\varphi(ij)\mu(ij) \\ =\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)\frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}\mu(ij) \\ =\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{\varphi(i)\varphi(j)gcd(i,j)^2}{\varphi(gcd(i,j))}\mu(ij) \\ =\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(i)\varphi(j)[gcd(i,j)=1]\mu(i)\mu(j) \\ =\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\varphi(i)\varphi(j)\mu(i)\mu(j) \\ =\sum_{d=1}^{min(n,m)}\mu(d)\sum_{d|i}^{n}\varphi(i)\mu(i)\sum_{d|j}^{m}\varphi(j)\mu(j) i=1nj=1mgcd(i,j)φ(ij)μ(ij)=i=1nj=1mgcd(i,j)φ(gcd(i,j))φ(i)φ(j)gcd(i,j)μ(ij)=i=1nj=1mφ(gcd(i,j))φ(i)φ(j)gcd(i,j)2μ(ij)=i=1nj=1mφ(i)φ(j)[gcd(i,j)=1]μ(i)μ(j)=i=1nj=1mdgcd(i,j)μ(d)φ(i)φ(j)μ(i)μ(j)=d=1min(n,m)μ(d)dinφ(i)μ(i)djmφ(j)μ(j)

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f

const int N=3e7;
const ll mod=1ll<<32;
ll sum1[N+5],sum2[N+5];
int prime[N+5],notPrime[N+5],mu[N+5],phi[N+5],cnt=0;
void init()
{
   
    mu[1]=phi[1]=1;
    for(int i=2;i<=N;i++)
    {
   
        if(!notPrime[i])
        {
   
            prime[++cnt]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&1ll*i*prime[j]<=N;j++)
        {
   
            notPrime[i*prime[j]]=1;
            if(i%prime[j])
            {
   
                mu[i*prime[j]]=-mu[i];
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
            else
            {
   
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}
int t,n,m;
int main()
{
   
    init();
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d%d",&n,&m);
        ll res=0;
        int M=min(n,m),Max=max(n,m);
        for(int i=1;i<=n;i++)sum1[i]=mu[i]*phi[i];
        for(int i=1;i<=m;i++)sum2[i]=mu[i]*phi[i];
        for(int i=1;i<=cnt&&prime[i]<=Max;i++)
        {
   
            for(int j=n/prime[i];j;j--)sum1[j]+=sum1[prime[i]*j];
            for(int j=m/prime[i];j;j--)sum2[j]+=sum2[prime[i]*j];
        }
        for(int i=1;i<=M;i++)
            res=(res+1ll*mu[i]*sum1[i]*sum2[i]%mod)%mod;
        res=(res+mod)%mod;
        printf("%lld\n",res);
    }
    return 0;
}