BZOJ 4173 数学

题面：

4173: 数学

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 602 Solved: 289
[Submit][Status][Discuss]

Description

Input

输入文件的第一行输入两个正整数。

Output

如题

Sample Input

5 6

Sample Output

240

HINT

N,M<=10^15

$nquad modquad k+mquad mod quad k>=k$

等价于 $n-lfloorfrac{n}{k} floor*k+m-lfloorfrac{m}{k} floor*k>=k$

$lfloorfrac{n+m}{k} floor-lfloorfrac{n}{k} floor-lfloorfrac{m}{k} floor=1$

$sum_{lfloorfrac{n+m}{k} floor-lfloorfrac{n}{k} floor-lfloorfrac{m}{k} floor=1}phi(k)$

$=sum_{k=1}^{n+m}phi(k)lfloorfrac{m+n}{k} floor-sum_{k=1}^{n}phi(k)lfloorfrac{n}{k} floor-sum_{k=1}^{m}phi(k)lfloorfrac{m}{k} floor$

$sum_{k=1}^{n}phi(k)lfloorfrac{n}{k} floor=sum_{k=1}^{n}phi(k)sum_{k|i}^{n}1=sum_{i=1}^{n}sum_{k|i}phi(k)$

$ecausesum_{k|i}phi(k)=i$

$ hereforesum_{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的**