H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P2260
D
e
s
c
r
i
p
t
i
o
n
Description
Description
P2834换个模数，此时模数不是质数
S
o
l
u
t
i
o
n
Solution
Solution
用
e
x
g
c
d
exgcd
exgcd或欧拉定理求逆元即可
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#include<algorithm>
#define LL long long
#define mod 19940417
using namespace std
;LL n
,m
,inv2
,inv6
,S1
,S2
,Ans
;
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline LL
sum1(LL x
){return x
*(x
+1)%mod
*inv2
%mod
;}
inline LL
sum2(LL x
){return x
*(x
+1)%mod
*(2*x
+1)%mod
*inv6
%mod
;}
signed main()
{
n
=read();m
=read();
if(n
>m
) n
^=m
,m
=n
^m
,n
^=m
;
inv2
=9970209;inv6
=3323403;
S1
=n
*n
%mod
;
for(register int l
=1,r
;l
<=n
;l
=r
+1)
{
r
=n
/(n
/l
);
S1
-=(sum1(r
)-sum1(l
-1)+mod
)%mod
*(n
/l
)%mod
;
S1
=(S1
+mod
)%mod
;
}
S2
=m
*m
%mod
;S2
=(S2
+mod
)%mod
;
for(register int l
=1,r
;l
<=m
;l
=r
+1)
{
r
=m
/(m
/l
);
S2
-=(sum1(r
)-sum1(l
-1)+mod
)%mod
*(m
/l
)%mod
;
S2
=(S2
+mod
)%mod
;
}
Ans
=S1
*S2
%mod
;
Ans
-=n
*n
%mod
*m
%mod
;Ans
=(Ans
+mod
)%mod
;
for(register int l
=1,r
;l
<=n
;l
=r
+1)
{
r
=min(n
/(n
/l
),m
/(m
/l
));
Ans
+=(sum1(r
)-sum1(l
-1)+mod
)%mod
*(m
*(n
/l
)%mod
+n
*(m
/l
)%mod
)%mod
;Ans
=(Ans
+mod
)%mod
;
Ans
-=(sum2(r
)-sum2(l
-1)+mod
)%mod
*(m
/l
)%mod
*(n
/l
)%mod
;Ans
=(Ans
+mod
)%mod
;
}
printf("%lld",Ans
);
}
