题面：

Description

Input

Output

Sample Input

Sample Output

HINT

Source

$n\quad mod\quad k+m\quad mod \quad k>=k$

等价于 $n-\lfloor\frac{n}{k}\rfloor*k+m-\lfloor\frac{m}{k}\rfloor*k>=k$

$\lfloor\frac{n+m}{k}\rfloor-\lfloor\frac{n}{k}\rfloor-\lfloor\frac{m}{k}\rfloor=1$

$\sum_{\lfloor\frac{n+m}{k}\rfloor-\lfloor\frac{n}{k}\rfloor-\lfloor\frac{m}{k}\rfloor=1}\phi(k)$

$=\sum_{k=1}^{n+m}\phi(k)\lfloor\frac{m+n}{k}\rfloor-\sum_{k=1}^{n}\phi(k)\lfloor\frac{n}{k}\rfloor-\sum_{k=1}^{m}\phi(k)\lfloor\frac{m}{k}\rfloor$

$\sum_{k=1}^{n}\phi(k)\lfloor\frac{n}{k}\rfloor=\sum_{k=1}^{n}\phi(k)\sum_{k|i}^{n}1=\sum_{i=1}^{n}\sum_{k|i}\phi(k)$

$\because\sum_{k|i}\phi(k)=i$

$\therefore\sum_{i=1}^{n}\sum_{k|i}\phi(k)=\sum_{i=1}^{n}i$

答案就是\phi(n)*\phi(m)*n*m

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define LL long long
 5 const LL mod=998244353;
 6 LL p(LL x)
 7 {
 8     LL ans=x;
 9     for(LL i=2;i*i<=x;i++)
10         if(x%i==0)
11         {
12             ans-=ans/i;
13             while(x%i==0)
14                 x/=i;
15         }
16     if(x>1)
17         ans-=ans/x;
18     return ans;
19 }
20 LL n,m;
21 int main()
22 {
23     scanf("%lld%lld",&n,&m);
24     printf("%lld",(((((p(n)%mod)*(p(m)%mod)))%mod)*(((n%mod)*(m%mod))%mod))%mod);
25 }

BZOJ 4173

感谢lc的**

BZOJ 4173 数学