QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#809924#3681. 模积和LaDeX100 ✓3ms3700kbC++17968b2024-12-11 18:17:482024-12-11 18:17:59

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 18:17:59]
  • 评测
  • 测评结果:100
  • 用时:3ms
  • 内存:3700kb
  • [2024-12-11 18:17:48]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL MOD = 19940417;
const LL inv6 = 3323403;
const LL inv2 = 9970209;
LL n, m;

LL Calc1(LL x, LL y) {
	LL ret = 0;
	for (LL l = 1, r; l <= y; l = r + 1) {
		r = min(y, x / (x / l));
		ret = (ret + (x / l) * (l + r) % MOD * (r - l + 1) % MOD * inv2 % MOD) % MOD;
	}
	return ret;
}

LL f(LL x) { return x * (x + 1) % MOD * (x * 2 + 1) % MOD * inv6 % MOD; }

LL Calc2(LL x, LL y) {
	LL ret = 0;
	for (LL l = 1, r; l <= x && l <= y; l = r + 1) {
		r = min(y / (y / l), x / (x / l));
		ret = (ret + (x / l) * (y / l) % MOD * (f(r) - f(l - 1)) % MOD) % MOD;
	}
	return ret;
}

LL Calc(LL x) {
	return x * x % MOD - Calc1(x, x);
}

int main() {
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m; 
	if (n > m) swap(n, m);
	LL Ans = Calc(n) * Calc(m) % MOD - n * n % MOD * m % MOD + m * Calc1(n, n)
		+ n * Calc1(m, n) - Calc2(n, m);
	Ans = (Ans + MOD) % MOD;
	cout << Ans;
	return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3660kb

input:

195 631


output:

13499636

result:

ok single line: '13499636'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3700kb

input:

64 10872681


output:

1651075

result:

ok single line: '1651075'

Test #3:

score: 10
Accepted
time: 1ms
memory: 3640kb

input:

75 135111825


output:

1099449

result:

ok single line: '1099449'

Test #4:

score: 10
Accepted
time: 1ms
memory: 3696kb

input:

63 116177601


output:

17215072

result:

ok single line: '17215072'

Test #5:

score: 10
Accepted
time: 1ms
memory: 3648kb

input:

405041 602225


output:

4906861

result:

ok single line: '4906861'

Test #6:

score: 10
Accepted
time: 1ms
memory: 3640kb

input:

727429 937589


output:

4099574

result:

ok single line: '4099574'

Test #7:

score: 10
Accepted
time: 2ms
memory: 3584kb

input:

70337281 243937321


output:

16331489

result:

ok single line: '16331489'

Test #8:

score: 10
Accepted
time: 2ms
memory: 3652kb

input:

136349929 257383657


output:

19504124

result:

ok single line: '19504124'

Test #9:

score: 10
Accepted
time: 3ms
memory: 3652kb

input:

539154474 305587405


output:

8781805

result:

ok single line: '8781805'

Test #10:

score: 10
Accepted
time: 3ms
memory: 3572kb

input:

719865785 277727262


output:

937958

result:

ok single line: '937958'