QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301973 | #3681. 模积和 | Unknown1508 | 0 | 7ms | 4136kb | C++20 | 2.1kb | 2024-01-10 14:57:07 | 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";
}
Details
Tip: Click on the bar to expand more detailed information
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'