UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189443#3372. axzx001100664ms9620kbC++11761b2023-10-04 11:22:032023-10-04 12:23:13

answer

#include <bits/stdc++.h>
using namespace std;
long long pri[1000005], p[100005], pos;
void eulers(int n) {
	for (int i = 2; i <= n; i++) {
		if (!pri[i]) p[++pos] = i;
		for (int j = 1; j <= pos && i * p[j] <= n; j++) {
			pri[i * p[j]] = 1;
			if (!(i % p[j])) break;
		}
	}
}
signed main() {
	long long n, i, T, cnt, lm;
	scanf("%lld", &T);
	eulers(1000000);
	while (T--) {
		cnt = 0;
		scanf("%lld", &n);
		lm = n;
		for (i = 1; p[i]*p[i] <= n; i++) {
			if (n % p[i] == 0) cnt++;
			while (n % p[i] == 0) n /= p[i];
		}
		if (n > 1) cnt++;
		lm++;
		for (i = 1; p[i]*p[i] <= lm; i++) {
			if (lm % p[i] == 0) cnt++;
			while (lm % p[i] == 0) lm /= p[i];
		}
		if (lm > 1) cnt++;
		printf("%lld\n", cnt);
	}
	return 0;
}
Source code, Language: C++11

Details

小提示：点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 15ms
memory: 9620kb

input:

4000
344
89
542
562
114
958
974
41
34
516
511
346
98
154
567
347
141
399
281
922
971
881
263
254
413...

output:

5
4
4
3
5
4
5
4
4
5
3
3
4
5
4
4
4
5
4
4
3
4
4
5
5
3
5
5
2
4
5
3
5
5
5
4
5
4
5
3
4
6
5
4
4
5
6
3
5
4
...

result:

ok 4000 numbers

Test #2:

score: 5
Accepted
time: 17ms
memory: 9620kb

input:

4000
385
644
425
361
617
89
329
80
612
129
889
276
921
167
303
59
39
131
641
967
698
244
991
378
8
8...

output:

5
6
5
3
4
4
6
3
4
5
5
4
4
4
4
4
4
4
4
3
4
4
3
4
2
6
4
5
3
3
4
3
3
4
6
4
4
5
5
3
5
4
4
4
4
4
4
4
4
5
...

result:

ok 4000 numbers

Test #3:

score: 5
Accepted
time: 16ms
memory: 9616kb

input:

4000
216
549
874
693
524
274
303
655
165
945
765
235
797
455
551
521
337
510
348
262
506
951
923
2
9...

output:

4
5
5
5
5
4
4
4
5
6
5
4
5
6
5
4
3
6
4
3
5
5
6
2
4
5
4
4
5
4
4
4
4
4
5
4
4
4
4
4
5
5
5
5
5
3
5
6
3
4
...

result:

ok 4000 numbers

Test #4:

score: 5
Accepted
time: 13ms
memory: 9620kb

input:

4000
915
512
399
980
250
746
934
487
795
187
238
538
366
838
600
953
570
421
894
355
811
873
613
389...

output:

5
3
5
5
3
4
5
3
5
4
4
4
4
3
4
4
5
3
5
4
4
5
3
5
4
4
4
3
2
4
3
3
4
3
4
5
5
5
4
3
4
4
4
4
5
5
3
5
5
4
...

result:

ok 4000 numbers

Test #5:

score: 5
Accepted
time: 15ms
memory: 9616kb

input:

4000
347
899
815
113
622
351
128
625
104
824
899
106
878
541
791
532
242
237
747
132
97
910
19
859
1...

output:

4
5
5
4
4
4
3
3
5
5
5
3
4
3
5
5
3
5
5
5
3
5
3
4
3
4
5
5
5
6
5
3
5
4
5
4
3
3
4
3
4
6
4
4
4
6
4
4
5
4
...

result:

ok 4000 numbers

Test #6:

score: 5
Accepted
time: 17ms
memory: 9620kb

input:

4000
529
662
915
297
283
375
185
965
100
414
134
421
710
537
542
944
346
843
622
988
16
643
357
875
...

output:

4
5
5
4
3
4
5
6
3
5
4
3
5
4
4
5
3
4
4
5
2
4
5
5
2
4
4
4
5
5
4
6
5
4
4
3
4
5
6
4
4
6
5
3
4
5
5
5
5
4
...

result:

ok 4000 numbers

Test #7:

score: 5
Accepted
time: 15ms
memory: 9616kb

input:

4000
935
712
701
897
852
889
633
882
936
425
330
228
77
491
241
671
632
410
686
361
589
761
831
583
...

output:

6
4
4
5
4
5
4
4
4
5
5
4
5
4
3
5
4
5
4
3
5
4
4
4
5
3
3
4
3
4
5
4
6
4
5
4
6
3
5
4
4
4
3
5
4
5
4
6
3
4
...

result:

ok 4000 numbers

Test #8:

score: 5
Accepted
time: 17ms
memory: 9616kb

input:

4000
667
434
355
699
852
724
873
153
154
601
929
400
625
71
180
16
533
210
976
140
793
181
214
768
3...

output:

4
6
4
5
4
4
5
5
5
4
5
3
3
3
4
2
5
5
3
5
4
4
4
3
4
5
4
4
3
4
6
4
4
4
4
6
5
6
5
4
6
3
5
5
5
4
5
4
6
5
...

result:

ok 4000 numbers

Test #9:

score: 5
Accepted
time: 18ms
memory: 9620kb

input:

4000
190
573
892
924
102
831
665
728
772
764
395
242
86
548
157
779
35
422
644
760
1
427
172
297
597...

output:

4
5
4
6
4
4
6
4
3
5
5
3
4
4
3
6
4
4
6
4
1
4
3
4
5
4
1
5
5
3
4
4
2
5
5
4
3
5
4
4
5
5
5
5
5
5
4
4
5
4
...

result:

ok 4000 numbers

Test #10:

score: 5
Accepted
time: 11ms
memory: 9620kb

input:

4000
934
510
519
944
614
229
183
506
363
204
890
855
199
474
22
51
338
292
178
215
668
442
841
452
6...

output:

5
6
5
5
5
4
4
5
5
5
5
5
3
5
3
4
4
3
3
4
4
4
3
4
4
4
4
4
5
5
4
4
4
4
4
5
4
5
5
5
2
5
4
3
5
4
4
5
4
4
...

result:

ok 4000 numbers

Test #11:

score: 5
Accepted
time: 52ms
memory: 9616kb

input:

4000
928329707
651873373
395002609
938733692
410051984
835706537
312655842
837280546
794308894
56162...

output:

6
5
7
9
7
5
6
5
4
7
6
5
4
9
4
5
7
7
6
6
4
7
7
6
5
6
6
4
6
6
6
6
7
7
7
8
5
6
10
6
6
7
6
8
10
7
7
5
7
...

result:

ok 4000 numbers

Test #12:

score: 5
Accepted
time: 49ms
memory: 9620kb

input:

4000
280020011
492291060
873139181
301191636
890824129
342108450
16691249
919211014
600047721
255963...

output:

6
6
4
5
7
6
6
6
8
4
7
8
4
5
5
8
6
6
6
7
6
8
4
7
7
7
6
6
7
10
6
6
6
8
8
9
5
6
6
4
11
9
6
6
8
7
6
5
6
...

result:

ok 4000 numbers

Test #13:

score: 5
Accepted
time: 53ms
memory: 9616kb

input:

4000
372745037
609565544
351053487
385046326
809132411
561675429
329448940
414517502
433906512
42144...

output:

7
7
4
4
7
8
7
9
6
6
6
6
6
6
9
8
7
8
8
6
7
5
8
6
6
5
6
9
7
7
6
6
7
6
6
4
3
8
7
7
7
6
5
9
7
6
6
6
6
8
...

result:

ok 4000 numbers

Test #14:

score: 5
Accepted
time: 48ms
memory: 9620kb

input:

4000
775371301
800503483
160496415
526978511
231889972
470136544
772784111
883101773
167658600
58704...

output:

4
7
6
7
7
9
8
8
6
5
7
6
7
8
5
6
7
7
7
6
4
9
6
7
5
5
7
6
9
8
7
7
9
6
9
5
6
7
4
6
6
6
6
5
8
5
6
5
9
8
...

result:

ok 4000 numbers

Test #15:

score: 5
Accepted
time: 49ms
memory: 9616kb

input:

4000
935220770
378470207
507531660
85453858
937252936
779750835
804597347
329948551
515774164
990937...

output:

7
5
8
4
5
6
5
5
9
7
7
9
5
6
8
6
7
5
4
6
6
7
5
5
8
7
7
10
6
6
7
5
4
5
8
8
5
4
4
8
6
6
5
4
9
5
7
7
6
8...

result:

ok 4000 numbers

Test #16:

score: 5
Accepted
time: 51ms
memory: 9620kb

input:

4000
636422886
68445824
931851346
821790650
457551915
283295681
48180751
735034044
439517537
1673654...

output:

7
8
6
8
10
6
6
8
6
6
7
7
8
6
6
5
8
5
6
10
7
7
7
6
9
8
7
6
5
7
6
9
5
9
7
9
7
8
6
5
5
5
5
9
7
6
6
6
4
...

result:

ok 4000 numbers

Test #17:

score: 5
Accepted
time: 51ms
memory: 9616kb

input:

4000
126495575
459321311
527748300
814587067
691261396
614113186
590027841
728790702
980129260
27759...

output:

6
5
6
6
5
6
6
8
6
7
5
6
5
10
5
8
7
6
7
7
10
6
8
7
7
9
5
8
7
7
7
7
6
8
7
6
5
6
8
9
8
7
4
6
7
7
6
5
7
...

result:

ok 4000 numbers

Test #18:

score: 5
Accepted
time: 51ms
memory: 9620kb

input:

4000
856075211
698307535
570944188
670644511
101004273
723690373
669193502
531727637
626451496
60755...

output:

5
5
7
6
7
9
8
8
6
6
7
5
6
7
7
6
7
5
4
7
7
7
8
7
6
7
7
7
8
5
9
7
5
7
10
6
7
6
4
6
4
8
6
8
6
5
7
6
6
6...

result:

ok 4000 numbers

Test #19:

score: 5
Accepted
time: 55ms
memory: 9620kb

input:

4000
10098149
722894582
33693347
192977404
977534574
767209615
604447828
172778536
322247201
7690070...

output:

6
6
6
7
6
6
4
4
7
6
7
6
10
7
8
6
7
7
8
7
6
7
4
9
9
7
6
6
9
6
4
8
9
7
5
6
7
6
7
7
6
9
9
5
6
8
5
6
7
7...

result:

ok 4000 numbers

Test #20:

score: 5
Accepted
time: 51ms
memory: 9620kb

input:

4000
673436299
257736388
103400395
329918163
725722920
907245478
487938001
75496272
608323217
886637...

output:

7
8
8
7
9
9
3
5
7
7
5
6
7
7
7
4
6
7
5
6
6
7
6
7
7
6
6
5
7
9
5
8
8
8
6
10
6
5
7
5
6
8
4
6
7
7
9
5
7
7...

result:

ok 4000 numbers

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-03-13 23:37:22 | 开源项目