QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178138#7046. Function!linninsAC ✓11ms1652kbC++141.5kb2023-09-13 18:31:212023-09-13 18:31:21

Judging History

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

  • [2023-09-13 18:31:21]
  • 评测
  • 测评结果：AC
  • 用时：11ms
  • 内存：1652kb
查看
  • [2023-09-13 18:31:21]
  • 提交

answer

#include <cstdio>
#include <cmath>
const int mp = 998244353;

const int ny2 = 499122177;
const int ny6 = 166374059;

int main(){
	//printf("%d\n", 6 * ny6 % mp);
	long long n;
	scanf("%lld", &n);
	int sqt = sqrt(n);
	long long ans = 0;
	for(long long a = 2; a <= sqt + 1; ++a){
		long long t = a;
		long long temp = 0;
		int temp2 = 1;
		while(t * a <= n){
			temp = (temp + (((t * a % mp - t + mp) % mp) * temp2) % mp) % mp;
			t = t * a;
			++temp2;
		}
		temp = (temp + ((n - t + mp + 1) % mp * temp2) % mp) % mp;
		ans = (ans + a * temp % mp) % mp;
	}
	if(sqt + 2 <= n){
		if(n & 1){
			long long p = sqt + 2;
			long long a = ((n + 1) / 2 - p + mp) % mp;
			long long b = (((n - 1) / 2) % mp);
			long long tp = ((n - p + 1 + mp) % mp) * (((((n + 1) / 2) % mp) * (((n + 1) / 2) % mp)) % mp) % mp;
			tp = (tp - (((a * (a + 1) % mp) * ((2 * a + 1) % mp) % mp) * ny6 % mp) + mp) % mp;
			tp = (tp - (((b * (b + 1) % mp) * ((2 * b + 1) % mp) % mp) * ny6 % mp) + mp) % mp;
			ans = (ans + tp) % mp;
		}
		else{
			long long p = sqt + 2;
			long long a = (n / 2) % mp;
			long long b = (a - p + mp) % mp;
			long long tp = (((((n - p + 1 + mp) % mp) * a) % mp) * a) % mp;
			tp = (tp + (((n + p) % mp) * ((n - p + 1 + mp) % mp) % mp) * ny2 % mp) % mp;
			tp = (tp - (((a * (a + 1) % mp) * ((2 * a + 1) % mp) % mp) * ny6 % mp) + mp) % mp;
			tp = (tp - (((b * (b + 1) % mp) * ((2 * b + 1) % mp) % mp) * ny6 % mp) + mp) % mp;
			ans = (ans + tp) % mp; 
		}
	} 
	printf("%lld", ans);
	return 0;
}
源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 1588kb

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1632kb

input:

10

output:

236

result:

ok 1 number(s): "236"

Test #3:

score: 0
Accepted
time: 0ms
memory: 1604kb

input:

20

output:

1646

result:

ok 1 number(s): "1646"

Test #4:

score: 0
Accepted
time: 0ms
memory: 1472kb

input:

27

output:

3862

result:

ok 1 number(s): "3862"

Test #5:

score: 0
Accepted
time: 0ms
memory: 1600kb

input:

37

output:

9571

result:

ok 1 number(s): "9571"

Test #6:

score: 0
Accepted
time: 0ms
memory: 1636kb

input:

100

output:

175028

result:

ok 1 number(s): "175028"

Test #7:

score: 0
Accepted
time: 0ms
memory: 1464kb

input:

123

output:

322744

result:

ok 1 number(s): "322744"

Test #8:

score: 0
Accepted
time: 0ms
memory: 1548kb

input:

2548

output:

765669726

result:

ok 1 number(s): "765669726"

Test #9:

score: 0
Accepted
time: 0ms
memory: 1632kb

input:

12448

output:

159637196

result:

ok 1 number(s): "159637196"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1636kb

input:

65535

output:

120089112

result:

ok 1 number(s): "120089112"

Test #11:

score: 0
Accepted
time: 0ms
memory: 1644kb

input:

102458

output:

475774506

result:

ok 1 number(s): "475774506"

Test #12:

score: 0
Accepted
time: 0ms
memory: 1628kb

input:

222333

output:

64337543

result:

ok 1 number(s): "64337543"

Test #13:

score: 0
Accepted
time: 0ms
memory: 1476kb

input:

485174

output:

312492357

result:

ok 1 number(s): "312492357"

Test #14:

score: 0
Accepted
time: 0ms
memory: 1460kb

input:

685479

output:

35530508

result:

ok 1 number(s): "35530508"

Test #15:

score: 0
Accepted
time: 0ms
memory: 1600kb

input:

1025481

output:

921523794

result:

ok 1 number(s): "921523794"

Test #16:

score: 0
Accepted
time: 0ms
memory: 1652kb

input:

9999999

output:

732610409

result:

ok 1 number(s): "732610409"

Test #17:

score: 0
Accepted
time: 0ms
memory: 1588kb

input:

7458658

output:

825346623

result:

ok 1 number(s): "825346623"

Test #18:

score: 0
Accepted
time: 0ms
memory: 1640kb

input:

5268475

output:

30938162

result:

ok 1 number(s): "30938162"

Test #19:

score: 0
Accepted
time: 0ms
memory: 1612kb

input:

2658478

output:

780038100

result:

ok 1 number(s): "780038100"

Test #20:

score: 0
Accepted
time: 0ms
memory: 1576kb

input:

10000000

output:

679483439

result:

ok 1 number(s): "679483439"

Test #21:

score: 0
Accepted
time: 0ms
memory: 1596kb

input:

100000000

output:

498142384

result:

ok 1 number(s): "498142384"

Test #22:

score: 0
Accepted
time: 0ms
memory: 1608kb

input:

1000000000

output:

69187994

result:

ok 1 number(s): "69187994"

Test #23:

score: 0
Accepted
time: 1ms
memory: 1632kb

input:

10000000000

output:

23566211

result:

ok 1 number(s): "23566211"

Test #24:

score: 0
Accepted
time: 3ms
memory: 1632kb

input:

100000000000

output:

247411531

result:

ok 1 number(s): "247411531"

Test #25:

score: 0
Accepted
time: 11ms
memory: 1620kb

input:

1000000000000

output:

434484365

result:

ok 1 number(s): "434484365"

Test #26:

score: 0
Accepted
time: 8ms
memory: 1476kb

input:

487456215487

output:

219915839

result:

ok 1 number(s): "219915839"

Test #27:

score: 0
Accepted
time: 2ms
memory: 1636kb

input:

123456654321

output:

873090152

result:

ok 1 number(s): "873090152"

Test #28:

score: 0
Accepted
time: 8ms
memory: 1604kb

input:

485623875512

output:

905855726

result:

ok 1 number(s): "905855726"

Test #29:

score: 0
Accepted
time: 8ms
memory: 1472kb

input:

598745632254

output:

548362077

result:

ok 1 number(s): "548362077"

Test #30:

score: 0
Accepted
time: 7ms
memory: 1576kb

input:

451518115487

output:

856104478

result:

ok 1 number(s): "856104478"
English 繁體中文 简体中文

服务器时间: 2024-12-02 21:33:12 | 开源项目