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