QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301973#3681. 模积和Unknown15080 7ms4136kbC++202.1kb2024-01-10 14:57:072024-01-10 14:57:07

Judging History

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

  • [2024-01-10 14:57:07]
  • 评测
  • 测评结果:0
  • 用时:7ms
  • 内存:4136kb
  • [2024-01-10 14:57:07]
  • 提交

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;
		}
	}
	cout << "sum_n = " << sum_n << "\n";
	{
		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: 0
Wrong Answer
time: 0ms
memory: 3568kb

input:

195 631


output:

sum_n = 6711
13499636

result:

wrong answer 1st lines differ - expected: '13499636', found: 'sum_n = 6711'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3696kb

input:

64 10872681


output:

sum_n = 693
1651075

result:

wrong answer 1st lines differ - expected: '1651075', found: 'sum_n = 693'

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 3804kb

input:

75 135111825


output:

sum_n = 981
1099449

result:

wrong answer 1st lines differ - expected: '1099449', found: 'sum_n = 981'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 3756kb

input:

63 116177601


output:

sum_n = 693
17215072

result:

wrong answer 1st lines differ - expected: '17215072', found: 'sum_n = 693'

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 3736kb

input:

405041 602225


output:

sum_n = -7241212
4906861

result:

wrong answer 1st lines differ - expected: '4906861', found: 'sum_n = -7241212'

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 3628kb

input:

727429 937589


output:

sum_n = -17218962
4099574

result:

wrong answer 1st lines differ - expected: '4099574', found: 'sum_n = -17218962'

Test #7:

score: 0
Wrong Answer
time: 4ms
memory: 3956kb

input:

70337281 243937321


output:

sum_n = 1297089
16331489

result:

wrong answer 1st lines differ - expected: '16331489', found: 'sum_n = 1297089'

Test #8:

score: 0
Wrong Answer
time: 2ms
memory: 3756kb

input:

136349929 257383657


output:

sum_n = -8586410
19504124

result:

wrong answer 1st lines differ - expected: '19504124', found: 'sum_n = -8586410'

Test #9:

score: 0
Wrong Answer
time: 6ms
memory: 4120kb

input:

539154474 305587405


output:

sum_n = -9097617
8781805

result:

wrong answer 1st lines differ - expected: '8781805', found: 'sum_n = -9097617'

Test #10:

score: 0
Wrong Answer
time: 7ms
memory: 4136kb

input:

719865785 277727262


output:

sum_n = -12043303
937958

result:

wrong answer 1st lines differ - expected: '937958', found: 'sum_n = -12043303'