题目传送门(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 <cstdio>#define ll long longconst 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原创, 转载必须以链接形式注明>原文链接<