QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#60693#3853. Lines in a gridSorting#AC ✓832ms316212kbC++902b2022-11-06 09:25:242023-09-24 13:54:06

Judging History

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

  • [2023-09-24 13:54:06]
  • 管理员手动重测该提交记录
  • 测评结果:AC
  • 用时:832ms
  • 内存:316212kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-06 09:25:25]
  • 评测
  • 测评结果:100
  • 用时:1652ms
  • 内存:316032kb
  • [2022-11-06 09:25:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int iu=1e7;
ll phi[iu+1];
const ll mod=1e6+3;
ll p0[iu+1],p1[iu+1],p2[iu+1];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	for(int i=1; i<=iu ;i++){
		phi[i]+=i;
		for(int j=i*2; j<=iu ;j+=i){
			phi[j]-=phi[i];
		}
	}
	p0[1]=p1[1]=p2[1]=1;
	for(int i=2; i<=iu ;i++){
		p0[i]=(p0[i-1]+phi[i]*2)%mod;
		p1[i]=(p1[i-1]+phi[i]*i%mod+phi[i]*i/2%mod)%mod;
		p2[i]=(p2[i-1]+phi[i]*i%mod*i%mod)%mod;
		//cout << p0[i] << ' ' << p1[i] << ' ' << p2[i] << endl;
	}
	int t;cin >> t;
	while(t--){
		ll n;cin >> n;
		if(n==1){
			cout << "0\n";
			continue;
		}
		ll ans=n;
		{
			ans=(ans-n*n%mod*p0[n/2]+4*p1[n/2]*n-4*p2[n/2])%mod;
			ans=(ans+n*n%mod*p0[n]-2*p1[n]*n+p2[n])%mod;
			ans=(ans+mod)%mod;
			
		}
		ans=(ans*2)%mod;
		cout << ans << '\n';
	}
}

详细

Test #1:

score: 100
Accepted
time: 818ms
memory: 316208kb

input:

10
1 2 3 4 5 6 7 8 9 10

output:

0
6
20
62
140
306
536
938
1492
2306

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 820ms
memory: 316064kb

input:

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

output:

0
6
20
62
140
306
536
938
1492
2306
3296
4722
6460
8830
11568
14946
18900
23926
29544
36510
44388
53586
63648
75674
88948
104374
121032
139966
160636
184466
209944
239050
270588
305478
342480
383370
427020
475830
527280
583338
642900
708798
777912
854022
934604
21071
111365
209991
313609
425767
5425...

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 817ms
memory: 316168kb

input:

1000
999000 999001 999002 999003 999004 999005 999006 999007 999008 999009 999010 999011 999012 999013 999014 999015 999016 999017 999018 999019 999020 999021 999022 999023 999024 999025 999026 999027 999028 999029 999030 999031 999032 999033 999034 999035 999036 999037 999038 999039 999040 999041 9...

output:

546070
193945
346418
377018
37466
751815
955839
157887
339995
522058
582121
473366
340311
290383
918701
862726
444011
438858
911955
921485
301270
699249
433065
907182
40424
772622
357721
211889
575810
629609
30983
876744
264169
808803
188203
748204
392664
267459
919490
320743
3927
490236
833633
9156...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 807ms
memory: 316076kb

input:

1000
453972 516606 570567 374049 422559 197777 181774 541268 5455 532617 559307 552527 174796 106684 506191 654637 48814 772908 150793 871094 187337 630103 682078 590953 456679 32784 755725 312523 235515 810164 520456 642283 616498 185466 836147 831550 261713 127618 85181 923213 33952 867185 130882 ...

output:

521457
552203
362377
520340
271000
96956
991169
901031
375542
93773
236463
744764
604355
557256
117961
512339
574575
562694
659733
287701
110161
860510
650908
740606
323739
321423
978238
159053
556787
24079
504173
566425
693719
158187
732866
614438
684481
821497
720603
866172
997262
403230
732268
82...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 820ms
memory: 316088kb

input:

1000
746388 708028 258366 416454 498990 90616 45928 840954 771202 75901 201827 663367 302208 908508 491895 856966 656450 563176 794405 140655 780889 646713 471035 308676 33396 438704 58210 809605 888367 100839 316212 881395 877323 45138 850544 797210 40000 440819 794639 926781 460222 17291 226354 85...

output:

825131
100250
25349
910410
710624
369637
98838
949978
409802
983803
854332
75645
843457
396665
430341
743675
571733
983824
436291
699539
760039
176823
176085
737980
434777
840310
60100
384098
799468
967137
537714
659755
4153
949560
897417
848197
489161
905487
914244
10800
753864
311218
179848
316220...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 806ms
memory: 316148kb

input:

1000
80775 511476 672923 825999 827426 482347 497984 568943 798803 166491 938151 14447 501355 423281 465997 297312 34439 824488 968980 467674 513959 242596 915128 822510 541867 211231 704722 824306 88541 770898 771094 312857 192490 907310 491183 24385 168119 698832 437638 305360 425730 330313 57684 ...

output:

431698
650163
625836
669564
562886
83648
181374
120479
251594
603609
325264
249583
379375
251675
181237
627004
45958
639029
636613
518362
853345
477236
17135
341433
163255
961849
207864
706325
253265
435180
997239
690726
763725
684994
682307
253163
219348
467170
997646
608245
648427
889917
626905
41...

result:

ok 1000 lines

Test #7:

score: 0
Accepted
time: 793ms
memory: 316212kb

input:

1000
9999000 9999001 9999002 9999003 9999004 9999005 9999006 9999007 9999008 9999009 9999010 9999011 9999012 9999013 9999014 9999015 9999016 9999017 9999018 9999019 9999020 9999021 9999022 9999023 9999024 9999025 9999026 9999027 9999028 9999029 9999030 9999031 9999032 9999033 9999034 9999035 9999036...

output:

678165
587960
566890
956174
697748
86527
226684
988507
787756
611376
969984
3498
821943
492596
818008
442858
366965
796460
151873
658416
318744
412768
63411
906506
664219
365337
535803
162829
245636
673258
548627
952301
739568
133837
162037
179254
36654
181961
196689
4292
997285
327583
631027
185992...

result:

ok 1000 lines

Test #8:

score: 0
Accepted
time: 832ms
memory: 316144kb

input:

3
1 3 2

output:

0
20
6

result:

ok 3 lines