一、题目
二、分析
参考文章：click here
具体的公式推导可以看参考文章。博主的证明很详细。
自己在写的时候问题不在公式推导，公式还是能够比较顺利的推导出来，但是，码力不够，比如说在乘积的时候，因为输入时候的$n$和$m$没有注意，一直用的$int$类型的，导致中间结果早就爆了，自己却浑然不知。
还有一个细节就是题目给的模数不是质数，所以求逆元的时候需要使用扩展欧几里得进行求解逆元。
三、AC代码
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 #define ll long long
5 #define Min(a,b) ((a)>(b)?(b):(a))
6 #define Max(a,b) ((a)>(b)?(a):(b))
7 const int mod = 19940417;
8 const int inv = 3323403;
9
10 void exgcd(ll a, ll b, ll &x, ll &y)
11 {
12 if(b == 0)
13 {
14 x = 1, y = 0;
15 return ;
16 }
17 else
18 {
19 ll x1, y1;
20 exgcd(b, a % b, x1, y1);
21 x = y1;
22 y = x1 - (a / b) * y1;
23 }
24 }
25
26 ll solve(ll n)
27 {
28 ll ans = (n % mod * n % mod) % mod;
29 ll L = 1, R;
30 for(L; L <= n; L = R + 1)
31 {
32 int k = n / L;
33 if(!k)
34 {
35 R = n;
36 }
37 else
38 {
39 R = n / k;
40 }
41 ans = (ans - (R - L + 1) * (L + R) / 2 % mod * k % mod + mod) % mod;
42 }
43 return ans;
44 }
45
46 ll get(ll n)
47 {
48 return n * (n + 1) % mod * (n<<1|1) % mod * inv % mod;
49 }
50
51 int main()
52 {
53 //exgcd(6, mod, x, y); //x就是6在mod下的逆元
54 ll n, m;
55 cin >> n >> m;
56 ll ans1, ans2, ans3, ans = solve(n) * solve(m) % mod;
57 if(n < m) swap(n, m);
58 ll L, R;
59 for(L = 1; L <= m; L = R + 1)
60 {
61 R = Min(n/(n/L), m/(m/L));
62 ans1 = (n*m % mod *(R - L + 1)) % mod;
63 ans2 = ((n/L) * m % mod + (m/L) * n % mod) % mod * ((R - L + 1) * (L + R) / 2 % mod) % mod;
64 ans3 = ((n/L) * (m/L) % mod * (get(R) - get(L - 1) + mod) % mod )% mod;
65 ans = ((ans - (ans1 + ans3 - ans2) ) % mod + mod) % mod;
66 }
67 printf("%lld\n", ans%mod);
68 return 0;
69 }