QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#486991#3681. 模积和KiharaTouma100 ✓3ms3944kbC++231.1kb2024-07-22 14:52:452024-07-22 14:52:50

Judging History

This is the latest submission verdict.

  • [2024-07-22 14:52:50]
  • Judged
  • Verdict: 100
  • Time: 3ms
  • Memory: 3944kb
  • [2024-07-22 14:52:45]
  • Submitted

answer

//qoj3681
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll P = 19940417, i2 = 9970209, i6 = 3323403;
ll n, m;

ll sm(ll x){
	x %= P;
	return x * (x+1) % P * i2 % P;
}
ll sm(ll l, ll r){
	return (sm(r) - sm(l-1) + P) % P;
}
ll pw(ll x){
	x %= P;
	return x * (x+1) % P * (x+x+1) % P * i6 % P;
}
ll pw(ll l, ll r){
	return (pw(r) - pw(l-1) + P) % P;
}
ll clc(ll x){
	ll ans = 0;
	for(ll l = 1, r; l <= x; l = r + 1){
		r = x / (x / l);
		ans = (ans + (x / l) % P * sm(l, r)) % P;
	}
	return ans;
}
ll calc(ll x, ll y){
	ll ans = 0;
	for(ll l = 1, r; l <= min(x, y); l = r + 1){
		r = min(x / (x / l), y / (y / l));
		ans += x * y % P * (r-l+1) % P;
		ans -= y * (x / l) % P * sm(l, r) % P;
		ans -= x * (y / l) % P * sm(l, r) % P;
		ans += (x / l) * (y / l) % P * pw(l, r) % P;
		ans = (ans % P + P) % P;
	}
	return ans;
}

int main(){
	scanf("%lld%lld", &n, &m);
	ll ans = 0;
	ans += (n * n % P + P - clc(n)) * (m * m % P + P - clc(m)) % P;
	ans -= calc(n, m);
	printf("%lld\n", (ans % P + P) % P);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

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

input:

195 631


output:

13499636

result:

ok single line: '13499636'

Test #2:

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

input:

64 10872681


output:

1651075

result:

ok single line: '1651075'

Test #3:

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

input:

75 135111825


output:

1099449

result:

ok single line: '1099449'

Test #4:

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

input:

63 116177601


output:

17215072

result:

ok single line: '17215072'

Test #5:

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

input:

405041 602225


output:

4906861

result:

ok single line: '4906861'

Test #6:

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

input:

727429 937589


output:

4099574

result:

ok single line: '4099574'

Test #7:

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

input:

70337281 243937321


output:

16331489

result:

ok single line: '16331489'

Test #8:

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

input:

136349929 257383657


output:

19504124

result:

ok single line: '19504124'

Test #9:

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

input:

539154474 305587405


output:

8781805

result:

ok single line: '8781805'

Test #10:

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

input:

719865785 277727262


output:

937958

result:

ok single line: '937958'