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

Myth丶恋晨 2023-08-17 17:04 54阅读 0赞

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

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/11423331.html