QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307587#8000. 平方数zhouyuhang70 555ms36616kbC++141.9kb2024-01-18 20:48:032024-01-18 20:48:04

Judging History

你现在查看的是测评时间为 2024-01-18 20:48:04 的历史记录

  • [2024-01-23 17:03:38]
  • hack成功,自动添加数据
  • (/hack/520)
  • [2024-01-23 14:31:04]
  • hack成功,自动添加数据
  • (/hack/519)
  • [2024-01-22 00:28:58]
  • hack成功,自动添加数据
  • (/hack/518)
  • [2024-01-21 22:26:07]
  • hack成功,自动添加数据
  • (/hack/516)
  • [2024-01-21 22:13:18]
  • hack成功,自动添加数据
  • (/hack/515)
  • [2024-01-21 19:47:46]
  • 管理员手动重测本题所有提交记录
  • 测评结果:70
  • 用时:567ms
  • 内存:36532kb
  • [2024-01-18 20:48:04]
  • 评测
  • 测评结果:70
  • 用时:555ms
  • 内存:36616kb
  • [2024-01-18 20:48:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using i128 = __int128_t;

const int N = 3e5 + 10;

int n;
i128 a[N];

i128 read() {
	i128 x = 0; int ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return x;
}

mt19937 Rnd(time(0));
int Rand(int l, int r) { return Rnd() % (r - l + 1) + l;} 
bool isPrime(int n) { for (int i = 2; i * i <= n; ++i) if (n % i == 0) return 0; return 1;}
int Pow(int x, int y, int p) {
	int r = 1;
	for (; y; y >>= 1, x = 1ll * x * x % p) if (y & 1) r = 1ll * r * x % p;
	return r;
}

i128 v[N];
vector<i128> val;
vector<int> vec[N];

bool np[N];
int tot = 0, prm[N];
int f[N];

int main() {
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	
	for (int t = 0; t < 100; ++t) {
		int p = Rand(1e4, 1e5);
		while (!isPrime(p)) p = Rand(1e4, 1e5);
		f[0] = f[1] = 1, tot = 0;
		for (int i = 2; i < p; ++i) {
			if (!np[i]) { prm[++tot] = i, f[i] = Pow(i, (p - 1) / 2, p);}
			for (int j = 1, t; (t = i * prm[j]) < p; ++j) {
				np[t] = 1, f[t] = 1ll * f[i] * f[prm[j]] % p;
				if (t % prm[j] == 0) break;
			}
		}
		for (int i = 1; i <= n; ++i) {
			v[i] ^= (f[a[i] % p] == 1 ? 0 : (i128)1) << t;
		}
	}
	for (int i = n; i >= 1; --i) v[i] ^= v[i + 1];
	
	for (int i = 1; i <= n + 1; ++i) val.push_back(v[i]);
	sort(val.begin(), val.end());
	for (int i = 1; i <= n + 1; ++i) v[i] = lower_bound(val.begin(), val.end(), v[i]) - val.begin();

	long long ans = 0;
	vec[0].push_back(n + 1);
	for (int i = n; i >= 1; --i) {
		ans += vec[v[i]].size();
		vec[v[i]].push_back(i);
	}
	
	cout << ans << endl;
	int cnt = 1e5;
	for (int i = 1; i <= n; ++i) {
		vec[v[i]].pop_back();
		for (int j = (int)vec[v[i]].size() - 1; j >= 0; --j) {
			if (cnt == 0) { return 0;}
			cout << i << ' ' << vec[v[i]][j] - 1 << endl;
			--cnt;
		}
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 275ms
memory: 16320kb

input:

100
231 1092 572 688 473 832 2132 861 1092 2132 451 451 861 473 336 473 231 231 832 231 1092 451 861 209 451 399 656 176 1328 3403 176 63 231 123 688 156 48 2236 6 6 231 572 572 231 57 399 48 176 1092 399 572 399 399 209 1743 1577 861 4316 399 451 1328 129 156 688 4316 4316 451 22 42 656 572 832 473...

output:

219
1 3
1 11
1 21
1 28
1 34
1 38
1 40
1 44
1 52
1 64
1 66
1 91
2 8
2 13
2 23
2 41
2 43
2 48
2 54
2 72
2 93
2 100
3 6
3 9
3 19
3 49
4 11
4 21
4 28
4 34
4 38
4 40
4 44
4 52
4 64
4 66
4 91
5 15
5 35
5 63
5 86
6 16
6 18
6 27
6 78
7 9
7 19
7 49
8 10
8 12
8 22
8 26
8 31
8 67
8 77
8 88
9 13
9 23
9 41
9 43
...

result:

ok 439 numbers

Test #2:

score: 5
Accepted
time: 275ms
memory: 16472kb

input:

100
175 175 423 423 315 1645 423 1067 1067 385 385 2425 2425 423 2400 275 9312 423 423 63 329 3395 960 960 250 423 970 875 4559 385 1067 1645 1067 1056 737 1645 6432 99 875 603 517 2400 1175 3360 670 517 1056 2400 470 63 63 385 225 350 90 2425 873 1645 873 873 960 1645 864 350 4559 250 3395 517 423 ...

output:

190
1 2
1 4
1 7
1 9
1 11
1 13
1 71
3 4
3 7
3 9
3 11
3 13
3 71
4 6
4 14
4 33
5 7
5 9
5 11
5 13
5 71
6 30
6 37
6 49
6 51
6 75
7 14
7 33
8 9
8 11
8 13
8 71
9 18
9 21
10 11
10 13
10 71
11 22
11 24
11 38
11 55
11 57
11 72
11 84
11 93
11 95
11 98
12 13
12 71
14 71
15 33
16 77
17 34
17 78
18 19
18 28
18 32...

result:

ok 381 numbers

Test #3:

score: 5
Accepted
time: 243ms
memory: 14492kb

input:

100
145 145 3976 3976 361 3976 3976 1159 1159 1159 3976 1159 95 95 1073 2257 551 25 1159 1159 1159 1691 445 1349 1624 280 2059 570 1830 3976 3976 1159 1073 445 2581 703 3976 95 3976 900 1159 4331 1064 6319 6319 2581 2581 95 3976 2130 95 1680 5041 1064 1102 2627 3382 95 4984 703 2059 551 2627 1073 28...

output:

282
1 2
1 4
1 5
1 7
1 9
1 38
1 43
1 45
1 47
1 52
1 53
1 69
1 74
1 76
1 79
1 93
2 25
2 62
2 70
2 72
2 99
3 4
3 5
3 7
3 9
3 38
3 43
3 45
3 47
3 52
3 53
3 69
3 74
3 76
3 79
3 93
4 6
4 12
4 14
4 19
4 21
4 27
4 32
4 39
4 40
4 65
4 77
5 5
5 7
5 9
5 38
5 43
5 45
5 47
5 52
5 53
5 69
5 74
5 76
5 79
5 93
6 7
...

result:

ok 565 numbers

Test #4:

score: 5
Accepted
time: 311ms
memory: 22908kb

input:

100000
490261 103622 581460 82 148675 57960 470171 480754 465750 67894 14094 386906 10507 2253 386074 89318 29184 633445 158738 616183 225862 13528 252387 378575 828099 563268 31578 487411 590795 156306 69611 483536 120028 615414 19244 49885 113293 33947 218039 86557 78069 13129 64829 193152 10489 6...

output:

412
62 3782
96 151
270 270
319 5502
337 1680
367 562
390 390
473 40115
650 650
814 814
923 923
1156 2670
1398 49930
1456 11214
1599 2107
1750 1750
2091 48791
2227 2227
2694 2694
2797 10608
2938 2938
3067 3067
3355 3355
3369 3369
3513 8600
3605 47519
3951 3951
4281 4281
4396 7330
4497 4497
4521 4521
...

result:

ok 825 numbers

Test #5:

score: 5
Accepted
time: 311ms
memory: 24692kb

input:

100000
67570 484736 520610 35657 3810 433919 234898 100380 364999 387610 203364 324993 3560 53217 324693 348977 456751 49183 149319 269122 252338 180787 146746 111557 60555 8843 352186 280066 23641 16419 341544 163445 103514 71100 37300 7087 757096 121635 375844 210450 21037 294544 205250 34189 6230...

output:

435
47 2598
47 2599
164 3171
313 6765
487 487
540 677
596 1128
668 668
1588 1588
1590 1590
1983 1983
2599 2599
2786 71013
2812 2812
2925 2925
3110 3110
3132 59588
3390 3390
3390 26703
3391 26703
3774 3774
3817 3817
3897 4061
3966 3966
4072 92911
4073 4073
4089 5255
4218 5589
4414 28043
4648 4648
466...

result:

ok 871 numbers

Test #6:

score: 5
Accepted
time: 310ms
memory: 20792kb

input:

100000
18881 262211 537680 17472 378696 709552 94019 77851 30857 149404 649543 170996 771720 10549 516075 228930 277507 624288 276892 297900 307159 359999 361232 113249 77423 147606 423604 84538 156003 90085 327367 855426 827139 61725 185473 372586 208861 231422 265506 141980 374872 1476 38531 54102...

output:

465
84 66713
167 167
206 3836
369 369
491 491
499 499
508 1165
676 7886
705 6687
920 920
1248 2110
1306 1306
1313 1313
1611 1611
2119 2119
2332 2332
2470 2470
2533 9957
2788 2788
2976 2976
3281 3281
3453 85306
3520 3520
3607 3607
3664 13904
3916 5491
3996 3996
4132 94587
4329 4329
4335 4335
4657 509...

result:

ok 931 numbers

Test #7:

score: 5
Accepted
time: 283ms
memory: 14704kb

input:

100
252540522668367800051165503341797101 252540522668367800051165503341797101 515734205540858375230970744185503476 515734205540858375230970744185503476 515734205540858375230970744185503476 20006351115008868016624085151101641 247729772684862577956704436312743764 525749426133479408507862683647100309 2...

output:

268
1 2
1 4
1 9
1 13
1 25
1 27
1 30
1 37
1 39
1 41
1 45
1 57
1 68
1 79
1 93
1 95
1 100
2 8
2 10
2 31
2 44
2 49
2 80
3 4
3 9
3 13
3 25
3 27
3 30
3 37
3 39
3 41
3 45
3 57
3 68
3 79
3 93
3 95
3 100
4 5
4 6
4 20
4 28
4 40
4 69
4 78
4 82
5 9
5 13
5 25
5 27
5 30
5 37
5 39
5 41
5 45
5 57
5 68
5 79
5 93
5 9...

result:

ok 537 numbers

Test #8:

score: 5
Accepted
time: 279ms
memory: 14540kb

input:

100
215586339034581112359324805094546001 303379817540300361137707126338995147 104808748941005778265379001474181311 624037066192891324650526373997894277 25241527443369969985568078141601980 25241527443369969985568078141601980 25241527443369969985568078141601980 246472575163277676212469646102580577 330...

output:

228
1 4
1 6
1 33
1 38
1 60
1 76
1 87
3 10
3 11
3 17
3 28
3 30
3 56
3 58
3 74
3 96
3 98
4 27
4 31
4 32
4 39
4 46
4 52
4 55
4 67
4 79
4 95
4 99
5 6
5 33
5 38
5 60
5 76
5 87
6 7
6 14
6 21
6 26
6 40
6 49
6 64
6 66
6 92
7 33
7 38
7 60
7 76
7 87
8 14
8 21
8 26
8 40
8 49
8 64
8 66
8 92
9 63
10 12
10 24
10 ...

result:

ok 457 numbers

Test #9:

score: 5
Accepted
time: 279ms
memory: 16148kb

input:

100
158537529361366175017273712129860802 158537529361366175017273712129860802 158537529361366175017273712129860802 19229228673961850397142728750194500 19229228673961850397142728750194500 158537529361366175017273712129860802 158537529361366175017273712129860802 146462580301387603768001461232863067 14...

output:

311
1 2
1 6
1 10
1 19
1 50
1 61
1 81
1 83
2 3
2 5
2 7
2 9
2 11
2 13
2 15
2 17
2 21
2 24
2 34
2 36
2 52
2 60
2 62
2 63
2 69
2 88
3 6
3 10
3 19
3 50
3 61
3 81
3 83
4 5
4 7
4 9
4 11
4 13
4 15
4 17
4 21
4 24
4 34
4 36
4 52
4 60
4 62
4 63
4 69
4 88
5 26
5 30
5 42
5 64
6 7
6 9
6 11
6 13
6 15
6 17
6 21
6 2...

result:

ok 623 numbers

Test #10:

score: 5
Accepted
time: 239ms
memory: 16372kb

input:

100
914638941914953504311998276428558213 914638941914953504311998276428558213 747095025403412259040087323520544846 742830945879368908514418916394107478 536433221656876669923408388652526923 522825554970208754487023674878950119 938444400048947160306314773841111921 285959233901776009120253190045112270 ...

output:

285
1 2
1 7
1 27
2 4
2 14
2 16
2 18
2 26
2 30
2 38
2 48
2 52
2 53
2 55
2 57
2 59
2 65
2 66
3 7
3 27
5 14
5 16
5 18
5 26
5 30
5 38
5 48
5 52
5 53
5 55
5 57
5 59
5 65
5 66
6 11
6 12
6 19
6 20
6 25
6 36
6 54
6 56
6 62
6 69
6 77
6 79
6 96
7 47
8 27
10 22
11 13
11 17
11 24
11 29
11 40
11 49
11 68
11 97
1...

result:

ok 571 numbers

Test #11:

score: 5
Accepted
time: 244ms
memory: 14752kb

input:

1000
291640644163858666081098032534898160 227357873561114642640834038516007202 13245561176000847812806783283096383 289847020373306548740443264748943677 289847020373306548740443264748943677 578552671736987388173788537730093157 6996821701676472759359784939297029 121600854669192376466073378531494349 40...

output:

64
4 5
5 14
13 34
14 47
14 249
21 409
32 187
37 93
37 929
40 102
40 146
41 816
46 258
47 597
48 249
50 64
55 83
55 455
61 518
79 125
79 422
84 455
86 170
94 929
103 146
107 718
117 207
126 422
133 222
136 159
136 270
143 310
149 347
160 270
177 946
211 289
212 324
217 832
221 333
247 496
248 368
264...

result:

ok 129 numbers

Test #12:

score: 5
Accepted
time: 243ms
memory: 16100kb

input:

1000
317806128212589382361485435548385354 597207142028658456258290616807422380 282499763987829361735046986098432002 24448882920496661495145116220484493 300550860888796946709885526447080103 33872715256434239525511448119212677 120942718535851021168502782891536521 157753857877561652333091326318512411 1...

output:

67
6 12
9 24
9 118
9 119
15 113
23 53
24 35
25 118
25 119
34 92
38 80
41 133
46 104
46 566
55 62
67 265
67 887
68 151
79 353
102 200
105 566
110 172
111 185
119 119
131 223
153 259
154 819
157 371
183 333
191 239
191 447
191 911
209 661
226 747
227 293
240 447
240 911
248 313
254 456
266 887
285 545...

result:

ok 135 numbers

Test #13:

score: 5
Accepted
time: 240ms
memory: 16112kb

input:

1000
175069690451769261445886256076778193 857377950130838290706851349542703 431074356670154777789431486369543688 246568169661771346881881284912665915 137955738264388301374432966342843643 501622433047900938246400117167545693 506556801796207331983983371075935 458676314832825522220021693067634300 72787...

output:

70
1 16
1 20
1 254
7 36
15 50
17 20
17 254
20 774
21 254
29 92
31 973
33 118
40 40
43 70
47 54
50 241
52 113
61 306
61 411
67 837
81 135
81 386
111 492
112 171
115 206
116 523
118 158
132 514
136 386
137 353
137 565
148 281
164 190
185 218
204 247
216 755
240 316
254 485
257 442
257 636
257 651
261 ...

result:

ok 141 numbers

Test #14:

score: 5
Accepted
time: 258ms
memory: 14540kb

input:

1000
617267984368402121547949873441168308 74192584480760102557741382968162984 423581651907322293415720778192460243 20860154602830400218895069317697272 121752740599378404172232949246702703 8480850023521496288452919096991489 12453086212561936481787210116074927 48248460229948537657399224672895337 65369...

output:

73
1 697
3 22
3 334
4 41
4 69
4 186
5 12
11 90
14 126
14 322
22 532
23 334
25 915
36 61
42 69
42 186
46 156
54 246
56 105
56 116
57 274
57 899
59 266
70 186
78 177
88 799
94 94
97 315
97 317
98 352
101 149
102 579
106 116
110 456
110 549
110 682
127 322
133 135
154 781
158 204
160 160
166 287
173 40...

result:

ok 147 numbers

Test #15:

score: 0
Wrong Answer
time: 355ms
memory: 24476kb

input:

100000
254265166806186183995767664564186160 276525657902692643693464830133973599 14597708679048712471331958616721616 359181801526616841850768359903202650 384064071764377152750283075761763137 167144655873360876803761918905939916 314660320441387223855132017820518857 46234119728759441422159276896429495...

output:

6
128 1340
190 415
211 676
1308 2631
6101 6130
94076 94076

result:

wrong answer 1st numbers differ - expected: '59', found: '6'

Test #16:

score: 0
Wrong Answer
time: 360ms
memory: 22840kb

input:

100000
64877618662819381351327782685017620 287251583192024472245732328155777164 81924196794087694863774077894446261 587898088473307245633470467109625817 63983457055859356681418342070232640 467531606610562532827526302618648017 156643527477744456327114323891851228 410775814992874901613953568756269400 ...

output:

14
40 40
175 850
392 1098
1246 1867
3089 8937
3362 4817
5072 5745
8302 10518
42530 42530
58470 58470
63238 63238
64881 65290
82014 82014
95579 95579

result:

wrong answer 1st numbers differ - expected: '67', found: '14'

Test #17:

score: 0
Wrong Answer
time: 353ms
memory: 24608kb

input:

100000
400382407579164630565570106786834592 598989994019780586622660096767873140 202713125527451525208506091402848040 306656951540312625601017432814883193 385533812806222459233700726433861948 114792968802667943882261595590188390 683453871393149097207519280770515051 6797074249509152378642958893459456...

output:

8
1545 2074
6389 6389
9132 10778
26776 26776
30755 30755
37492 37835
53301 53301
92158 92158

result:

wrong answer 1st numbers differ - expected: '62', found: '8'

Test #18:

score: 0
Wrong Answer
time: 545ms
memory: 35992kb

input:

300000
11979100587810800802923349735474971 384568989741449185758732548398537465 692031101896121489295510142056399609 174419831569051368765733330998938852 72675424159770430711139346222466676 792926893016443498788235028652731500 131899888836396741244415546802600120 449365951867691934494751253423827525...

output:

5
10 21
588 1971
12090 12090
46732 46732
203763 203763

result:

wrong answer 1st numbers differ - expected: '55', found: '5'

Test #19:

score: 0
Wrong Answer
time: 555ms
memory: 36616kb

input:

300000
13159476220540052611063099704777119 404069210783480886299855108899917825 606724469975551403885266994483701254 161478011836648686548748736172102098 191126570380800476556975432074751901 15799586089681007279542308115871748 121959472970612542582013529465554644 289381348752343543671715423172520800...

output:

1
8551 8648

result:

wrong answer 1st numbers differ - expected: '54', found: '1'

Test #20:

score: 0
Wrong Answer
time: 555ms
memory: 36340kb

input:

300000
711310443416742782431396964084452 1303778642379799335236750513539496 1235880107471962090842032248476135 1815830256757580411001511688032056 1646915814259921137430603642187095 2066825075807731605894416184650449 110919427936977169221309066929877 1896880667099287111024124058694220 139227650014149...

output:

4
4397 4492
24647 24647
24770 24770
38778 39517

result:

wrong answer 1st numbers differ - expected: '57', found: '4'