题意：

给定\(n,m,p\)，求

\[\sum_{a=1}^n\sum_{b=1}^m\frac{\varphi(ab)}{\varphi(a)\varphi(b)}\mod p
\]

思路：

由欧拉函数性质可得：\(x,y\)互质则\(\varphi(xy)=\varphi(x)\varphi(y)\)；\(p\)是质数则\(\varphi(p^a)=(p-1)^{a-1}\)。因此，由上述两条性质，我们可以吧\(a,b\)质因数分解得到

\[\begin{aligned}
\sum_{a=1}^n\sum_{b=1}^m\frac{\varphi(ab)}{\varphi(a)\varphi(b)}\mod p&=\sum_{a=1}^n\sum_{b=1}^m\frac{gcd(a,b)}{(p_1 - 1)(p_2-1)\dots (p_k-1)}\mod p\\
&=\sum_{a=1}^n\sum_{b=1}^m\frac{gcd(a,b)}{\varphi(gcd(a,b))}\mod p\\
&=\sum_{k}\sum_{k|d}\mu(\frac{d}{k})F(d)*k*inv[\varphi(k)] \mod p
\end{aligned}
\]

有点卡常。

代码：

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<ctime>

#include<cmath>

#include<cstdio>

#include<string>

#include<vector>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e6 + 5;

const int INF = 0x3f3f3f3f;

const ull seed = 131;

const ll MOD = 1000000007;

using namespace std;

int mu[maxn], vis[maxn];

int prime[maxn], cnt, phi[maxn];

ll inv[maxn];

void init(int n){

    for(int i = 0; i <= n; i++) vis[i] = mu[i] = 0;

    cnt = 0;

    mu[1] = 1;

    phi[1] = 1;

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

        if(!vis[i]){

            prime[cnt++] = i;

            mu[i] = -1;

            phi[i] = i - 1;

        }

        for(int j = 0; j < cnt && prime[j] * i <= n; j++){

            vis[prime[j] * i] = 1;

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

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

                break;

            }

            mu[i * prime[j]] = -mu[i];

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

        }

    }

}

void init2(int n, ll p){

    inv[0] = inv[1] = 1;

    for(int i = 2; i <= n; i++)

        inv[i] = (p - p / i) * inv[p % i] % p;

}

int main(){

    init(1e6);

    int T;

    scanf("%d", &T);

    while(T--){

        ll n, m, p;

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

        ll mm = min(n, m);

        init2(mm, p);

        ll ans = 0;

        for(int k = 1; k <= mm; k++){

            ll temp = 0;

            for(int d = k; d <= mm; d += k){

                temp += 1LL * mu[d / k] * (n / d) * (m / d);

            }

            temp = temp * k % p * inv[phi[k]] % p;

            ans = (ans + temp) % p;

        }

        ans = (ans + p) % p;

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

    }

    return 0;

}

巴特西

HDU 6390 GuGuFishtion（莫比乌斯反演 + 欧拉函数性质 + 积性函数）题解

题意：

思路：

代码：

最新文章

热门文章