BZOJ 4173: 数学 – [欧拉函数]

题目传送门(BZOJ)

题解 :

来人, 上式子!

n\%k+m\%k \ge k \Leftrightarrow \lfloor\frac{n+m}{k}\rfloor-\lfloor\frac{n}{k}\rfloor-\lfloor\frac{m}{k}\rfloor = 1

我们可以把前面的\varphi(n)\times \varphi(m)​先放在一边最后算

那么ans = \sum\limits_{n\%k+m\%k\ge k}\varphi(k)

即

\sum\limits_{k=1}^{n+m}\varphi(k)\times\lfloor\frac{n+m}{k}\rfloor-\sum\limits_{k=1}^{n}\varphi(k)\times \lfloor\frac{n}{k}\rfloor-\sum\limits_{k=1}^{m}\varphi(k)\times \lfloor\frac{m}{k}\rfloor

令f(n)=\sum\limits_{k=1}^{n}\varphi(k)\times \lfloor\frac{n}{k}\rfloor

可以发现 :

\sum\limits_{i=1}^ni = \sum\limits_{i=1}^n\sum\limits_{k|i}\varphi(k)

优先枚举k可得

\sum\limits_{i=1}^n\sum\limits_{k|i}\varphi(k) = \sum\limits_{k=1}^{n}\varphi(k)\times \lfloor\frac{n}{k}\rfloor

故

f(n) = \sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}

f(n+m)-f(n)-f(m)=n\times m

这时候我们把之前丢掉的两个\varphi拿回来

ans = \varphi(n)\times\varphi(m)\times n\times m\mod 998244353

O\sqrt n求欧拉函数裸题

代码 :

#include 
#define ll long long
const int p = 998244353;
inline ll phi(ll n) {
    ll res = n;
    for(ll i = 2; i*i <= n; i ++ ) if(n%i == 0) {
        res = res/i*(i-1);
        while(n%i == 0) n/=i;
    }
    if(n > 1) res = res/n*(n-1);
    return res%p;
}
int main() {
    ll n, m; scanf("%lld%lld", &n, &m);
    printf("%lld\n", n%p*(m%p)%p*phi(n)%p*phi(m)%p);
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<