50pts求助
查看原帖
50pts求助
406941
Register_int-std=c++14楼主2022/7/24 13:30

rt.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 19940417;
const int inv6 = 3323403;

inline ll s1(ll n) { return (n * (n + 1) >> 1) % mod; }
inline ll s2(ll n) { return n * (n + 1) % mod * (n << 1 | 1) % mod * inv6 % mod; }

inline ll sum1(ll l, ll r) { return (s1(r) - s1(l - 1) + mod) % mod; }
inline ll sum2(ll l, ll r) { return (s2(r) - s2(l - 1) + mod) % mod; }

ll n, m;

ll p, q, t;

int main() {
	scanf("%lld%lld", &n, &m);
	p = n * n % mod;
	for (ll l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		p = (p - sum1(l, r) * (n / l) % mod + mod) % mod;
	}
	q = m * m % mod;
	for (ll l = 1, r; l <= m; l = r + 1) {
		r = m / (m / l);
		q = (q - sum1(l, r) * (m / l) % mod + mod) % mod;
	}
	t = n * n % mod * m % mod;
	for (ll l = 1, r; l <= min(n, m); l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		t = (t - sum1(l, r) * ((n / l) * m % mod + (m / l) * n % mod) + mod) % mod;
		t = (t + sum2(l, r) * (n / l) % mod * (m / l) % mod) % mod;
	}
	printf("%lld", (p * q - t) % mod);
}
2022/7/24 13:30
加载中...