QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301975#3681. 模积和Unknown1508100 ✓6ms4212kbC++202.1kb2024-01-10 14:57:372024-01-10 14:57:37

Judging History

This is the latest submission verdict.

  • [2024-01-10 14:57:37]
  • Judged
  • Verdict: 100
  • Time: 6ms
  • Memory: 4212kb
  • [2024-01-10 14:57:37]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long
const int mod = 19940417;
const int inv2 = (mod + 1) / 2;
const int inv6 = (mod + 1) / 6;

int n, m;
vector<int> events;

void split(int x){
	for (int i = 1, lim = 0; i <= x; i = lim + 1){
		lim = x / (x / i);
		events.push_back(lim + 1);
	}
}

int range_sum(int l, int r){
	return (l + r) * (r - l + 1) % mod * inv2 % mod;
}

int prefix_squared(int x){
	if (x <= 0) return 0;
	return x * (x + 1) % mod * (x * 2 + 1) % mod * inv6 % mod;
}

int range_sum_squared(int l, int r){
	return (prefix_squared(r) - prefix_squared(l - 1)) % mod;
}

void main_program(){
	cin >> n >> m;

	split(n); split(m);
	events.push_back(n);
	events.push_back(m);

	sort(events.begin(), events.end());
	events.resize(unique(events.begin(), events.end()) - events.begin());

	int sum_n = 0, sum_m = 0, sum_nm = 0;
	{
		int L = 1;
		int& total = sum_n;
		for (auto nxt: events){
			int R = nxt - 1;
			if (L > R) continue;
			if (L > n) continue;

			int val = n / L;
			int sum = n * (R - L + 1) % mod - val * range_sum(L, R) % mod;
			total = (total + sum) % mod;

			L = nxt;
		}
	}
	{
		int L = 1;
		int& total = sum_m;
		for (auto nxt: events){
			int R = nxt - 1;
			if (L > R) continue;
			if (L > m) continue;

			int val = m / L;
			int sum = m * (R - L + 1) % mod - val * range_sum(L, R) % mod;
			total = (total + sum) % mod;

			L = nxt;
		}
	}
	{
		int L = 1;
		int& total = sum_nm;
		for (auto nxt: events){
			int R = nxt - 1;
			if (L > R) continue;
			if (L > min(n, m)) continue;

			int ndiv = n / L, mdiv = m / L;
			int sum = n * m % mod * (R - L + 1) % mod
				- n * mdiv % mod * range_sum(L, R) % mod
				- m * ndiv % mod * range_sum(L, R) % mod
				+ ndiv * mdiv % mod * range_sum_squared(L, R) % mod;

			total = (total + sum) % mod;

			L = nxt;
		}
	}

	int res = sum_n * sum_m % mod - sum_nm;
	cout << (res % mod + mod) % mod << "\n";
}

詳細信息

Test #1:

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

input:

195 631


output:

13499636

result:

ok single line: '13499636'

Test #2:

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

input:

64 10872681


output:

1651075

result:

ok single line: '1651075'

Test #3:

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

input:

75 135111825


output:

1099449

result:

ok single line: '1099449'

Test #4:

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

input:

63 116177601


output:

17215072

result:

ok single line: '17215072'

Test #5:

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

input:

405041 602225


output:

4906861

result:

ok single line: '4906861'

Test #6:

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

input:

727429 937589


output:

4099574

result:

ok single line: '4099574'

Test #7:

score: 10
Accepted
time: 4ms
memory: 3812kb

input:

70337281 243937321


output:

16331489

result:

ok single line: '16331489'

Test #8:

score: 10
Accepted
time: 4ms
memory: 3796kb

input:

136349929 257383657


output:

19504124

result:

ok single line: '19504124'

Test #9:

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

input:

539154474 305587405


output:

8781805

result:

ok single line: '8781805'

Test #10:

score: 10
Accepted
time: 6ms
memory: 4212kb

input:

719865785 277727262


output:

937958

result:

ok single line: '937958'