GuGuFishtion HDU - 6390 （欧拉函数，容斥）

时间：2023-03-09 20:20:48
GuGuFishtion HDU - 6390 （欧拉函数，容斥）

GuGuFishtion

\[Time Limit: 1500 ms\quad Memory Limit: 65536 kB
\]

题意

给出定义\(Gu(a, b) = \frac{\phi(ab)}{\phi(a)\phi(b)}\)

求出\(\sum_{a=1}^{m}\sum_{b=1}^{n}Gu(a,b) (mod p)\)

思路

首先对于欧拉函数，我们知道欧拉函数的朴素式子为：\(\phi(n) = n*(1-\frac{1}{p1})*(1-\frac{1}{p2}) * ... * (1-\frac{1}{pn})\)，\(pi\) 为 \(n\) 的质因子。

对于任意两个数 \(a,b\)，令 \(g = gcd(a, b)\)

  1. 若 \(g != 1\)，令 \(pi\) 为 \(a\) 特有的质因子，\(qi\) 为 \(b\) 特有的质因子，\(ti\) 为\(a,b\) 共有的质因子，那么将 \(Gu(a, b)\) 展开，就可以得到

\[\begin{aligned}
Gu(a, b) &= \frac{\phi(ab)}{\phi(a)\phi(b)}\\
&= \frac{ab \prod(1-\frac{1}{pi}) \prod(1-\frac{1}{ti}) \prod(1-\frac{1}{qi}) }{a \prod(1-\frac{1}{pi}) \prod(1-\frac{1}{ti}) b \prod(1-\frac{1}{qi})\prod(1-\frac{1}{ti})} \\
&= \frac{1}{\prod(1-\frac{1}{ti})}
\end{aligned}
\]

现在我们设 \(x\)，\(x\) 包括了所有的 \(ti\)，那么就有

\[\begin{aligned}
Gu(a, b) &= \frac{1}{\prod(1-\frac{1}{ti})} \\
&= \frac{x}{x\prod(1-\frac{1}{ti})} \\
&= \frac{x}{\phi(x)}
\end{aligned}
\]

\(x\) 也很好知道是多少，其实 \(g\) 就满足同时包括了所有 \(ti\) 的数，所以我们可以设 \(x = g\)，就可以得到 \(Gu(a,b) = \frac{g}{\phi(g)}\)。

2. 若 \(g=1\)，此时不存在 \(ti\)，但这是 \(Gu(a, b)\) 展开后全部消掉了，所以答案为 \(1\)，而 \(\frac{1}{\phi(1)}\) 也正好为 \(1\)，所以也可以看成 \(Gu(a,b) = \frac{g}{\phi(g)}\)。

综合上述，\(Gu(a,b) = \frac{g}{\phi(g)}\)。

此时我们只要计算出 \(gcd(a, b) = x (a\in [1,m], b\in[1,n])\) 的对数，就可以直接计算答案了。

这里可以利用经典的莫比乌斯反演，也可以利用容斥原理。

令：

\(f(i)\) 表示 \(gcd\) 等于 \(i的倍数\) 的对数

\(g(i)\) 表示 \(gcd\) 等于 \(i\) 的对数

那么就有

\[f(i) = \lfloor\frac{m}{i}\rfloor \lfloor\frac{n}{i} \rfloor \\
g(i) = f(i) - \sum_{j=2}^{i*j<=min(n,m)} g(ij)
\]

如此倒着计算 \(g(i)\)，就可以得出答案。

Hint

emmmm，这题其实有点卡常，要注意取模的次数和自然数逆元打表的姿势。

/***************************************************************

    > File Name    : a.cpp

    > Author       : Jiaaaaaaaqi

    > Created Time : 2019年08月26日 星期一 16时58分58秒

 ***************************************************************/

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pb         push_back

#define  pii        pair<int, int>

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 1e6 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

ll n, m;

int cas, tol, T;

int pri[maxn], phi[maxn];

bool ispri[maxn];

ll f[maxn], g[maxn], inv[maxn];

void handle() {

    int mx = 1e6;

    mes(ispri, 1);

    tol = 0;

    phi[1] = 1;

    for(int i=2; i<=mx; i++) {

        if(ispri[i]) {

            pri[++tol] = i;

            phi[i] = i-1;

        }

        for(int j=1; j<=tol&&i*pri[j]<=mx; j++) {

            ispri[i*pri[j]] = 0;

            if(i%pri[j] == 0) {

                phi[i*pri[j]] = phi[i]*pri[j];

                break;

            } else {

                phi[i*pri[j]] = phi[i]*(pri[j]-1);

            }

        }

    }

}

int main() {

    // freopen("in", "r", stdin);

    handle();

    inv[1] = 1;

    scanf("%d", &T);

    while(T--) {

        ll p;

        scanf("%lld%lld%lld", &n, &m, &p);

        ll x = min(n, m);

        for(int i=2; i<=x; i++) inv[i] = (p-p/i)*inv[p%i]%p;

        for(int i=1; i<=x; i++) f[i] = (n/i)*(m/i)%p;

        for(int i=x; i>=1; i--) {

            g[i] = f[i];

            for(int j=2; i*j<=x; j++) {

                g[i] -= g[i*j];

                if(g[i]<0)  g[i]+=p;

            }

        }

        ll ans = 0;

        for(int i=1; i<=x; i++) {

            ans += 1ll*g[i]*i%p * inv[phi[i]]%p;

            ans %= p;

        }

        printf("%lld\n", ans);

    }

    return 0;

}

相关文章