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

「BZOJ4173」数学

原文：https://www.cnblogs.com/HenryHuang-Never-Settle/p/11688771.html