题意：
给定(n、m)，求
[sum_{i=1}^n sum_{j=1}^m (n \% i) *(m\%j) ag{i != j}
]
mod 19940417 的值
(n、m)是正整数（吧）， 最大规模(1e9)。
题解
[sum_{i=1}^n sum_{j=1}^m (n \% i) *(m\%j) ag{i != j}
]
[=sum_{i=1}^n ig(n - i* lfloor frac{n}{i}
floor ig) sum_{j=1}^m ig(m - j* lfloor frac{m}{j}
floor ig) -
]
[sum_{i=1}^{min(n,m)} ig(n - i* lfloor frac{n}{i}
floor ig) * ig(m - i* lfloor frac{m}{i}
floor ig)
]
分别用数论分块求和就好。
注意事项：19940417不是素数， 但其与2和6都互质。
洛谷数据AC代码 (丑的一匹不建议看)
#include<bits/stdc++.h>
using namespace std;
#define li long long
const int mod = 19940417;
const li inv2 = 9970209ll;
const li inv6 = 3323403ll;
//19940417 = 7*2848631
li gbk(li n) {
li res=0ll;
for(li l=1,r;l<=n;l=r+1) {
r = min(n,n/(n/l));
res += (l+r)*(r-l+1)%mod *(n/l)%mod *inv2 %mod;
res %= mod;
}
res = n*n%mod - res;
return ((res%mod+mod)%mod);
}
li gbk2(li n, li m) {
li len = min(n,m);
li res1 = len*n%mod*m%mod;
li res2 = 0ll, res3 = 0ll, res4 = 0ll;
for(li l=1,r;l<=len;l=r+1) {
r = min(len,n/(n/l));
res2 += (l+r)*(r-l+1)%mod *(n/l)%mod *inv2 %mod;
res2 %= mod;
}
for(li l=1,r;l<=len;l=r+1) {
r = min(len,m/(m/l));
res3 += (l+r)*(r-l+1)%mod *(m/l)%mod *inv2 %mod;
res3 %= mod;
}
for(li l=1,r;l<=len;l=r+1) {
r = min(n/(n/l), m/(m/l)); r=min(r,len);
li k = r*(r+1)%mod *(2*r+1)%mod *inv6%mod;
k -= (l-1)*l %mod *(2*l-1)%mod *inv6%mod;
res4 += k*(n/l)%mod*(m/l)%mod;
res4%=mod;
}
res2 = res2*m%mod, res3=res3*n%mod;
li res = res1-(res2+res3)%mod;
res %= mod;
res += res4;
res %= mod;
return ((res%mod+mod)%mod);
}
int main() {
li n, m; cin>>n>>m;
li nbk=gbk(n), mbk=gbk(m);
li nmbk=gbk2(n, m);
li ans = nbk*mbk%mod - nmbk%mod;
cout << ((ans%mod+mod)%mod);
return 0;
}