GuGuFishtion(欧拉函数公式+莫比乌斯)

2018-08-14

GuGuFishtion

题意

求：
$$
Ans=\sum_{i=1}^{n}\sum_{j=1}^m\frac{φ(ij)}{φ(i)φ(j)}%p
$$
其中，n,m<=1e6, max(n,m)<=p<=1e9，且p为素数。

##思路

由欧拉函数公式：
$$
φ(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})…(1-\frac{1}{p_n})，其中p_i为x的质因子
$$
将公式带入$\frac{φ(ij)}{φ(i)φ(j)}$中：
$$
原式=\frac{ij(1-\frac{1}{c_1})…(1-\frac{1}{c_t})}{i(1-\frac{1}{a_1})…(1-\frac{1}{a_n})j(1-\frac{1}{b_1})…(1-\frac{1}{b_m})}
$$

$$
=\frac{1}{(1-\frac{1}{a_1})(1-\frac{1}{a_2})…(1-\frac{1}{b_1})(1-\frac{1}{b_2})…}
$$

上下同乘以gcd(i,j)，则可以得到：

(这里虽然讲不清楚但是大致是一个容斥)
$$
原式=\frac{gcd(i,j)}{gcd(i,j)-gcd(i,j)/质因数的任意组合+gcd(i,j)/所有质因子的组合}
$$

$$
=\frac{gcd(i,j)}{φ(gcd(i,j))}
$$

因此
$$
Ans=\sum_{i=1}^{n}\sum_{j=1}^m\frac{gcd(i,j)}{φ(gcd(i,j))}%p
$$
令k=gcd(i,j)，并枚举k，有：
$$
Ans=\sum_{i=1}^{n}\sum_{j=1}^m\sum_{k=1}^{min(n,m)}\frac{k}{φ(k)}[gcd(i,j)==k]%p
$$

$$
=\sum_{k=1}^{min(n,m)}\frac{k}{φ(k)}\sum_{i=1}^{n}\sum_{j=1}^m[gcd(i,j)==k]%p
$$

$$
=\sum_{k=1}^{min(n,m)}\frac{k}{φ(k)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)==1]%p
$$

$$
=\sum_{k=1}^{min(n,m)}\frac{k}{φ(k)}\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}
\sum_{d=1}^{min(n,m)}μ(d)%p
$$

$$
=\sum_{k=1}^{min(n,m)}\frac{k}{φ(k)}\sum_{d=1}^{min(n,m)}μ(d){\lfloor\frac{n}{dk}\rfloor}{\lfloor\frac{m}{dk}\rfloor}%p
$$

就可以做啦！

枚举k=1~min(n,m)，先分析出要预先求的东西：

μ(d)
φ(k)

预处理：由于n/dk向下取整时，当dk>n，值为0，因此我们只要先枚举dk=1到min(n,m)即可。

然后对于for(k)，dk为d的倍数增长，此时，d=dk/k,将μ(dk/k)、n/dk、m/dk相乘，取模得到F(k)+=。

计算：然后就可以一个大循环，枚举k从1~min(n,m)，求得k*逆元(φ(k))，再*先前求得的F(k)，并取模即可。

注意：由于时间限制，取模一定要尽量少取。特别是在预处理阶段中，求F(k)时，由于F(k)是重复累加的，因此若是每一次累加都取模，会造成不必要的时间浪费，因此我们可以把F(k)开long long，然后在全部预处理完毕之后再一次性for取模。

看！代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD;
const int maxn = 1000000 + 5;
int phi[maxn],mu[maxn],prim[maxn];
bool vis[maxn]={0};

ll quzheng[maxn],f[maxn];
int cnt=0;
ll ex_gcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得（扩展gcd）
{
	if (a==0&&b==0) return -1;
	if (b==0){x=1;y=0;return a;}
	ll d=ex_gcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

ll mod_inverse(ll a,ll n)//乘法逆元，a与n必须互素
{
	ll x,y;
	ll d = ex_gcd(a,n,x,y);
	return (x%n+n)%n;
}

/** 对于μ函数的线筛 */
void get_mu(int n)
{
    mu[1]=phi[1]=1;
	for(int i=2;i<=n;i++)
	{
    	if(!vis[i]){prim[++cnt]=i;mu[i]=-1;phi[i]=i-1;}
   	 	for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
        {
        	vis[prim[j]*i]=1;
        	if(i%prim[j]==0) {phi[i*prim[j]]=phi[i]*prim[j];break;}
        	else {mu[i*prim[j]]=-mu[i];phi[i*prim[j]] = phi[i] * phi[prim[j]];}
    	}
	}

}

int cal(int n,int m)
{
    memset(f,0,sizeof(f));
    int MIN=min(n,m);
    for(int i=1;i<=MIN;i++) quzheng[i]=1ll*(n/i)*(m/i);
    for(int i=1;i<=MIN;i++)
        for(int j=i;j<=MIN;j+=i)
            f[i]+=1ll*mu[j/i]*quzheng[j];
    for(int i=1;i<=MIN;i++) //就是这个TLE
        f[i]%=MOD;
}

int main()
{
    int n,m,t;
    get_mu(1000000);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%lld",&m,&n,&MOD);
        cal(n,m);
        int MIN=min(n,m);
        ll ans=0;
        for(int i=1;i<=MIN;i++)
        {
            ans=(ans+(1ll*i*mod_inverse(phi[i],MOD))%MOD*f[i]+MOD)%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}