「BZOJ4173」数学

「BZOJ4173」数学

题目大意：

求
\[\varphi(n) \cdot \varphi(m) \cdot \sum_{k \in S(n,m)} \varphi(k)\ \mathrm{mod} \ 998244353\]
其中 \(S(n,m)\) 为满足 $ m \mathrm{mod}  k + n \mathrm{mod}  k \ge k$ 的 \(k\) 的集合。

我们可以对 $ m \mathrm{mod}  k + n \mathrm{mod}  k \ge k$ 进行化简。
\[m-\lfloor \frac{m}{k} \rfloor*k + n-\lfloor \frac{n}{k} \rfloor*k \ge k \\m+n \ge k(1+\lfloor \frac{m}{k} \rfloor + \lfloor \frac{n}{k} \rfloor) \\\lfloor \frac{m+n}{k} \rfloor -\lfloor \frac{m}{k} \rfloor - \lfloor \frac{n}{k} \rfloor= 1\\\]
即 $ m \mathrm{mod}  k + n \mathrm{mod}  k \ge k \iff \lfloor \frac{m+n}{k} \rfloor -\lfloor \frac{m}{k} \rfloor - \lfloor \frac{n}{k} \rfloor= 1$

令 $t=\sum_{k \in S(n,m)} \varphi(k)  \mathrm{mod}  998244353 $

则
\[t= \sum_{k=1}^{n+m} \varphi(k) \cdot [\ \lfloor \frac{m+n}{k} \rfloor -\lfloor \frac{m}{k} \rfloor - \lfloor \frac{n}{k} \rfloor \ ] \\=\sum_{k=1}^{n+m} \varphi(k) \cdot \ \lfloor \frac{m+n}{k} \rfloor -\sum_{k=1}^{m}\varphi(k) \cdot\lfloor \frac{m}{k} \rfloor - \sum_{k=1}^{n}\varphi(k) \cdot\lfloor \frac{n}{k} \rfloor\ \\\]
考虑求解 \(\sum_{k=1}^{Q}\varphi(k)\cdot\lfloor \frac{Q}{k} \rfloor\)

则其等于
\[\sum_{k=1}^{Q}\varphi(k)\cdot\lfloor \frac{Q}{k} \rfloor\\=\sum_{k=1}^{Q} \sum_{t=1}^{t<=\lfloor \frac{Q}{k} \rfloor} \varphi(k)\\=\sum_{t=1}^{Q} \sum_{k|t} \varphi(k)\\=\sum_{t=1}^{Q} t\]
于是有 \(ans= \varphi(n) \cdot \varphi(m) \cdot n \cdot m\)

时间复杂度 \(O(\sqrt{n})\)

贴代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=998244353;
ll eular(ll n){
    ll ans=n;
    ll i=2;
    while(i*i<=n){
        if(n%i==0){
            while(n%i==0) n/=i;
            ans=ans/i*(i-1);
        }
        ++i;
    }
    if(n!=1) ans=ans/n*(n-1);
    return ans%p;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll n,m;
    cin>>n>>m;
    cout<<(n%p*(m%p)%p*eular(n)%p*eular(m)%p)%p;
    return 0;
}