简单题

简单题

题意：

求：
$$\sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j)\phi (ij)\mu (ij)$$
多组数据。
为了减小输出大小，你只需输出上式模$2^{32}$的值

Solution：

首先知道一些函数的特点:
$$\begin{gathered} \phi (ij)=\frac{\phi (i)\phi (j)gcd(i,j)}{\phi (gcd(i,j))} \\ \mu (ij)=\mu (i)\mu (j)[gcd(i,j)=1] \end{gathered}$$
那么
$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j)\phi (ij)\mu (ij) \\ =\sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j)\frac{\phi (i)\phi (j)gcd(i,j)}{\phi (gcd(i,j))}\mu (ij) \\ =\sum _{i=1}^n\sum _{j=1}^m\frac{\phi (i)\phi (j)gcd(i,j{)}^2}{\phi (gcd(i,j))}\mu (ij) \\ =\sum _{i=1}^n\sum _{j=1}^m\phi (i)\phi (j)[gcd(i,j)=1]\mu (i)\mu (j) \\ =\sum _{i=1}^n\sum _{j=1}^m\sum _{d|gcd(i,j)}\mu (d)\phi (i)\phi (j)\mu (i)\mu (j) \\ =\sum _{d=1}^{min(n,m)}\mu (d)\sum _{d|i}^n\phi (i)\mu (i)\sum _{d|j}^m\phi (j)\mu (j) \end{gathered}$$

代码：

#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;
}