[数论分块] [清华集训2012]模积和

题目地址
对于 ${\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^m\left(n\%i\right)\ast \left(m\%j\right)(i!=j)}}$i=1∑n​j=1∑m​(n%i)∗(m%j)(i!=j)
可以先不管i!=j的条件，所以我们可以算 ${\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^m\left(n\%i\right)\ast \left(m\%j\right)}}$i=1∑n​j=1∑m​(n%i)∗(m%j)的情况。
我们知道 $n\%i=n-\left(\frac{n}{i}\right)\ast i$n%i=n−(in​)∗i，所以 ${\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^m\left(n\%i\right)\ast \left(m\%j\right)}}$i=1∑n​j=1∑m​(n%i)∗(m%j) = ${\displaystyle \sum _{i=1}^n(n-(\frac{n}{i})\ast i)\sum _{j=1}^m(m-(\frac{m}{j})\ast j)}$i=1∑n​(n−(in​)∗i)j=1∑m​(m−(jm​)∗j)。
所以答案就是 ${\displaystyle \sum _{i=1}^n(n-(\frac{n}{i})\ast i){\displaystyle \sum _{j=1}^m(m-(\frac{m}{j})\ast j)}}$i=1∑n​(n−(in​)∗i)j=1∑m​(m−(jm​)∗j)- ${\sum }_{i=1}^{min(n,m)}(n-i\ast (\frac{n}{i}\left)\right)\ast (m-i\ast (\frac{m}{i}\left)\right)$∑i=1min(n,m)​(n−i∗(in​))∗(m−i∗(im​))
前面的式子可以很好的解决，对于后面的的式子 ${\displaystyle \sum _{i=1}^{min(n,m)}(n-i\ast (\frac{n}{i}\left)\right)\ast (m-i\ast (\frac{m}{i}\left)\right)}$i=1∑min(n,m)​(n−i∗(in​))∗(m−i∗(im​))可以处理出 ${\displaystyle \sum _{i=1}^{min(n,m)}(n\ast m-i\ast m\ast (\frac{n}{i})-i\ast (\frac{m}{i})-i^2\ast (\frac{m}{i})\ast (\frac{n}{i}\left)\right)}$i=1∑min(n,m)​(n∗m−i∗m∗(in​)−i∗(im​)−i2∗(im​)∗(in​))其中n*m与 $i\ast m\ast \left(\frac{m}{i}\right)$i∗m∗(im​)与 $i\ast n\ast \left(\frac{n}{i}\right)$i∗n∗(in​)可以直接分块每次算出块中的等差数列就行了，剩下的 $i^2\ast \left(\frac{m}{i}\right)\ast \left(\frac{n}{i}\right)$i2∗(im​)∗(in​)考虑分块的话，应该用 $1^2$12+ $2^2$22+ $3^3$33+…+ $n^n$nn = $\frac{n\ast (n+1)\ast (2\ast n+1)}{6}$6n∗(n+1)∗(2∗n+1)​。由于要对答案取模，所以要算出6的逆元，乘上逆元就行了。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 19940417;
int Case = 1;
ll n, m;
ll cal(ll x) {
	ll res = x*x%mod;
	for(ll i = 1, j; i <= x; i = j+1) {
		j = min(x/(x/i), x);
		res = (res-(i+j)*(j-i+1)/2%mod*(x/i)%mod+mod)%mod;
	}
	return res;
}
ll query(ll x) {
	return x*(x+1)%mod*(2*x+1)%mod*3323403%mod;
}
void solve() {
    scanf("%lld%lld", &n, &m);
    ll t = min(n, m), res = cal(n)*cal(m)%mod;
    res = (res-n*m%mod*t%mod);
    while(res<0) res += mod;
    for(ll i = 1, j; i <= t; i=j+1) {
    	j = min(n/(n/i), m/(m/i));
    	ll s1 = (n/i)*(m/i)%mod*(query(j)-query(i-1)+mod)%mod;
    	ll s2 = (j-i+1)*(j+i)/2%mod*(n/i*m%mod+m/i*n%mod);
    	res = (res + (s2-s1)%mod + mod)%mod;
    }
    printf("%lld\n", res);
    return;
}

int main() {
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    //freopen("/Users/hannibal_lecter/Desktop/code/in.txt", "r", stdin);
    //freopen("/Users/hannibal_lecter/Desktop/code/out.txt","w",stdout);
#endif
    while(Case--) {
        solve();
    }
    return 0;
}