A - Football Loser

看清总评价的计算公式后利用 struct 和 sort 排序即可。

为了避免精度误差，建议按 k=(2m+n)tk=(2m+n)t（将原来的公式除以 0.030.03）计算总评价，此时需要使用 long long。（当然了，直接使用 double 或 long double 也是一个不错的选择。）

#include <bits/stdc++.h>
using namespace std;
const int A = 20 + 2;
struct Team
{
	string b;
	int m;
	int n;
	int t;
	long long k;
};
Team team[A];
bool cmp(Team x, Team y)
{
	return x.k > y.k;
}
int main()
{
	freopen("football.in", "r", stdin);
	freopen("football.out", "w", stdout);
	int T;
	cin >> T;
	while (T--)
	{
		int a;
		cin >> a;
		for (int i = 1; i <= a; i++)
		{
			cin >> team[i].b >> team[i].m >> team[i].n >> team[i].t;
			team[i].k = 1ll * team[i].t * (2ll * team[i].m + 1ll * team[i].n);
		}
		sort(team + 1, team + a + 1, cmp);
		for (int i = 1; i <= a; i++)
		{
			cout << team[i].b;
			if (i != a) cout << ' ';
		}
		cout << endl;
	}
	return 0;
}

B - Tangent Dancer

显然 d,φ≠0d,\varphi \ne 0。考虑一次移动中轨迹的斜率 k=tan⁡φφk=\dfrac{\tan \varphi}{\varphi}。画图可知，当 $\varphi \in (-\dfrac{\pi}{2},0) \cup (0,\dfrac{\pi}{2})$ 时，k∈(1,+∞)k \in (1,+\infty)：

也就是说，如果直线 ABAB 的斜率 kAB>1k_{AB}>1 且存在，那么就可以从 AA 一次性移动到 BB。

很明显，如果我们第一次移动时选择 d=10100,φ=π4d=10^{100},\varphi=\dfrac{\pi}{4}，那么一次移动后的位置 XX 与终点 YY 之间的斜率将会极其接近 4π\dfrac{4}{\pi}，显然可以从 XX 一次性移动到 YY。整个过程一共移动了 22 次，所以答案总是不超过 22。

综上，本题的结论是（设 PP 为起点，QQ 为终点）：

  • PP 与 QQ 重合时答案为 00；
  • kPQ>1k_{PQ}>1 且存在时答案为 11；
  • 以上两个条件都不满足时答案为 22。
#include <bits/stdc++.h>
using namespace std;
#define y1 Y1
int steps(int x1, int y1, int x2, int y2)
{
	if (x1 == x2 && y1 == y2) return 0;
	if (x2 > x1 && y2 - y1 > x2 - x1) return 1;
	if (x1 > x2 && y1 - y2 > x1 - x2) return 1;
	return 2;
}
int main()
{
	freopen("tangent.in", "r", stdin);
	freopen("tangent.out", "w", stdout);
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << steps(x1, y1, x2, y2) << endl;
	return 0;
}

C - Lottery Cheater

由题意可以列出一个 nn 元异或方程组，且每个方程中只有 22 个未知数。直接钦定任意一个值后用代入法递归解方程即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
bool ok[N], ans[N];
int n, k;
string s;
void fill(int i)
{
	if (ok[i]) return;
	ok[i] = true;
	int next = (i + k) % n;
	ans[next] = ans[i] ^ (s[next] - '0');
	fill(next);
}
int main()
{
	freopen("lottery.in", "r", stdin);
	freopen("lottery.out", "w", stdout);
	cin >> n >> k >> s;
	reverse(s.begin(), s.end());
	k %= n;
	for (int i = 0; i <= n - 1; i++)
		fill(i);
	for (int i = n - 1; i >= 0; i--)
		putchar(ans[i] + '0');
	return 0;
}

D - Factorial Master

首先特判 n≤2n \le 2 的情况。

很明显，当 x≥nx \ge n 时，n∣x!n\mid x!，因此答案不可能大于 n−1n-1。

当 nn 为质数时，由威尔逊定理可得：

(n−1)!≡−1 ( mod  n)(n-1)! \equiv -1\ (\bmod\ n) (n−1)!≡n−1 ( mod  n)(n-1)! \equiv n-1\ (\bmod\ n) (n−2)!≡1 ( mod  n)(n-2)! \equiv 1\ (\bmod\ n)

因此答案一定是 n−2n-2。

当 nn 为合数时，由题意可知 p∤x!p\nmid x!，其中 pp 是 nn 的最小素因子。

显然 p≤np \le \sqrt{n}，并且答案不大于 p−1p-1，暴力枚举即可。

最终的时间复杂度是 O(Tn)O(T\sqrt{n})。

#include <bits/stdc++.h>
using namespace std;
bool prime(int n)
{
	if (n == 1) return false;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;
	return true;
}
int solve(int n)
{
	if (n <= 2) return n - 1;
	if (prime(n)) return n - 2;
	long long f = 1;
	int ans = 1;
	for (int i = 2; n % i != 0; i++)
	{
		f = f * i % n;
		if (f == 1) ans = i;
	}
	return ans;
}
int main()
{
	freopen("factorial.in", "r", stdin);
	freopen("factorial.out", "w", stdout);
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		cout << solve(n) << endl;
	}
	return 0;
}

E - Proof Writer

若某个 01 串 AA 不满足第二个条件：

$$A_1\sharp(A_2\sharp(A_3\sharp(\cdots\sharp(A_{N-1}\sharp A_N))))=0 $$$$A_2\sharp(A_3\sharp(\cdots\sharp(A_{N-1}\sharp A_N)))=0\ (A_1=1) $$$$A_3\sharp(\cdots\sharp(A_{N-1}\sharp A_N))=0\ (A_2=1) $$…\ldots AN−1♯AN=0A_{N-1}\sharp A_N=0

因此只有 S=111…110S=\tt{111\ldots110} 不满足第二个条件。很明显，SS 同时也不满足第一个条件，所以第二个条件实际上是多余的。

对于第一个条件，设答案为 f(N)f(N)：

  • 如果 AN=1A_N=1，那么一定满足条件，共有 2N−12^{N-1} 个合法 01 串；
  • 如果 AN=0A_N=0，那么需要有 $((((A_1\sharp A_2)\sharp A_3)\sharp\cdots)\sharp A_{N-2})\sharp A_{N-1}=0$，共有 2N−1−f(N−1)2^{N-1}-f(N-1) 个合法 01 串。

结合 f(1)=1f(1)=1，我们得到了 f(N)f(N) 的递推公式：

$$f(N)=\begin{cases}1,&N=1\\2^N-f(N-1),&N\ge 2\end{cases} $$

由数学归纳法即可证明通项公式。

(D+) - Factorial Grandmaster

在原版做法的基础上，我们通过打表（或者查 OEIS A049048）可以发现，对应答案不为 11 的合数只有 21072107 个。于是我们可以先用 Miller-Rabin（选取 2,7,612,7,61 为底数判断三次）做素性判断，再对合数查表（查不到说明答案为 11）。该做法的时间复杂度为 O(Tlog⁡n)O(T \log n)。

#include <bits/stdc++.h>
using namespace std;
map<int, int> table;
const string TABLE =
R"(
996818003 12611
995994551 18704
993710489 22289
992943131 14343
992703487 663
992106239 22271
988778957 569
988516369 23455
988413071 13461
987936349 2549
986096173 623
985206779 17943
984991919 22191
984932411 6672
984182447 231
982099291 29031
981865057 12341
979930297 8721
979672979 22131
979075949 459
977182067 30647
977055251 11775
976379527 16001
974497049 29919
973838777 22065
973485749 22061
971192627 22035
970663829 22029
968730331 4215
968440373 25631
966110923 18519
965911127 21975
965586649 21879
961925693 741
961858081 881
961476421 10649
961406777 9179
959866573 3105
959708381 4086
958541219 21891
956463953 15401
954029303 5747
953768047 16425
953485543 17135
949033139 16475
948061739 21771
947676571 29151
946146749 21749
944967271 6299
944844191 22367
944059877 21725
943861543 17354
942383311 851
938045291 10091
938010583 6308
936390437 9465
936055027 15604
935786807 20403
933835589 8259
932256161 11120
931720627 12471
930987047 57
930730991 8441
930150787 12515
928430819 3431
927065443 11148
926119697 18057
924693509 21501
922600501 13061
921333713 27395
921159619 10863
918367691 17541
917707801 13870
915593227 3623
914626649 14085
914528011 128
912567781 10889
912567437 23369
910595237 265
909276689 21321
908563099 1996
906513667 9657
906239819 10372
905572897 4484
903009649 4740
902806277 21245
902330003 5571
900427867 16647
898639103 16475
895105489 16559
894766583 9753
891535217 10597
889147621 26249
887806123 7892
886426483 10430
882750719 22737
880203179 14230
879605317 19509
878513939 19721
875568413 3026
875508259 1603
872886451 5410
872470877 20885
871732241 1050
871692883 17517
870773413 1731
868507427 18948
868400983 16869
866877433 24849
863779591 17291
863322727 6055
862972739 20771
862806569 20769
862590767 22071
860720893 24681
860099561 19833
856146691 11015
853611337 8373
851949031 27939
849538357 12839
849433649 16695
846473519 25241
845472721 3977
845436167 1229
843001277 18403
841489573 8351
841012577 20505
838053329 17634
837944791 19425
837731669 3123
835771169 20441
835607639 20439
834739753 25799
834026429 13097
833569423 10935
833275249 21009
833156609 20409
831858241 17159
831712109 15425
829920607 97
828011543 25451
827890783 105
825353479 23079
824170859 12249
823875527 20295
823796879 8615
823597043 8251
823380133 14925
822764821 17319
822209137 4854
820933433 7295
818963569 2391
818772739 20518
818711911 4338
818526029 20229
817528709 1047
815202211 3494
814162127 20175
810842231 29
809669717 1607
808917127 12444
808777867 12149
808710667 1751
805879309 14745
804025049 20049
802913093 15049
802289941 17495
801620819 20019
801217199 1335
800213903 1037
799339049 1047
799229609 13889
799220189 19989
798117949 272
795906493 15
788859059 19859
788597393 4616
788518909 7079
787271039 19839
786109217 18537
785914121 18585
785340607 27959
785050499 19811
781919741 16296
780196993 13175
780144749 19749
774624479 19679
773910031 6381
773063521 7586
770606327 15491
769449011 401
768655729 483
768026027 19595
766964179 2367
765636427 585
765463793 15159
762623377 1317
762525427 26554
762249941 7565
759881257 27041
757558349 19461
756765661 16034
755358691 43
755286221 5145
754758377 19425
754535449 281
754292219 19419
753196589 191
752574983 7239
750036323 15677
748550039 10779
747917623 2163
747590189 10449
744475493 4480
744039983 2169
743373067 2696
742839239 19271
741987017 3385
740933813 2446
740405257 7157
738951989 15765
738669989 21011
736152727 3123
735344551 17441
734976409 2555
734695067 21267
734653961 915
733315753 9627
732371677 15887
732280823 5169
731301287 6909
730331513 18837
729235459 9885
728375419 4563
727405309 6671
727223323 21177
726662669 7602
726047129 24021
725970709 431
724101947 20895
723365177 676
721352603 329
721200427 25251
718646363 5236
717607529 3963
717565061 19539
717110587 2121
716726771 899
716352359 1191
715614421 155
715083893 16205
711517129 1750
711407783 9939
711056999 14138
710715233 20549
707006221 10611
706807721 15911
705846377 18785
705126073 11505
704688041 7346
702543869 18741
702159127 6365
701742607 14765
697558591 4109
697293041 8285
696231707 15629
694202573 10449
694080559 13645
694056617 3010
693917723 12192
693390673 25307
691504447 505
689312177 676
687742883 9596
687480877 10348
687389449 431
687065273 6027
685906163 6749
685188727 11184
684666509 18501
684413773 25069
683688023 11015
683668987 10449
681789571 10139
680823449 18449
679126043 2551
678785509 65
678543911 10695
676844027 18395
676657867 17181
676505737 9780
676154659 17541
676028083 3909
675547681 12639
674692541 23165
674656439 6908
674428891 832
672972499 19539
671854199 14765
670604531 5885
670254173 10863
670108487 1108
669798299 18299
669284773 22717
669033481 1516
668773877 18285
668693203 5957
668131349 3537
664046917 22227
661524203 9849
660737257 5005
658177133 1049
657988843 48
657556979 18131
657429281 10322
657205961 1533
657121877 18125
656073521 15371
654948527 18095
654759311 9717
653685889 7671
653501627 18075
652152811 7319
648796783 37
646922699 4364
644853827 17955
644852783 4131
644762917 20639
644143439 25347
642365149 2711
642270719 17919
642122077 13054
641051903 2129
639406679 17879
638607947 4361
638442713 2501
638093773 8698
638089303 8115
635768411 3051
632759359 6005
632298839 3677
632257211 4505
630976943 17181
630718483 1598
630481249 9717
629943103 18141
629858777 17745
629044769 2547
628353697 13107
628059319 21755
627447599 17711
627385397 6459
627325561 20847
624866653 16425
624291743 16785
623678359 2644
619368241 21699
617318881 12551
616350313 640
616022549 17549
615575089 272
615322459 6077
614771713 16925
613225061 4677
613220633 15953
612217913 15677
611378321 7751
611209073 2283
610313071 4300
608834069 4155
608776183 22191
608610917 2056
606170687 7219
605907559 4505
605876363 9677
605795543 5283
604086887 6766
601368539 17339
601130263 20591
599612443 5890
598648697 4612
598043819 17291
597891067 12965
597298157 7527
597119623 21557
596881777 8037
596145367 2108
593637749 3033
592469321 19062
591977849 14387
590039063 1421
589527349 15669
589127743 5333
587139221 8561
586476377 19137
586022167 10461
585932027 17115
584290019 17091
582707407 8465
582273827 19839
579022243 15906
578993537 13737
578697209 17009
578460679 12123
578375593 16013
576336031 14523
575946187 90
575435849 16961
574472273 2241
572995877 16925
572760913 14049
572448101 1335
571393007 16551
571342507 3299
570732047 401
569210669 16869
567155417 841
566897567 15642
565997921 6269
565895851 570
565169009 16809
564400267 3907
562938011 905
561341323 5705
560732021 1520
560471939 16739
559715291 4722
559548097 22077
558751133 1705
558202961 2547
558051671 2241
557930309 16701
557340989 1431
557061737 1319
556869853 3021
556731391 3040
556378861 15573
556368721 111
555927839 16671
555468259 9389
551763833 4390
551545861 429
551535077 16605
551430961 12147
549881051 1457
548483759 16559
547258003 1425
546667477 13791
546639271 15119
544501961 7701
542092049 342
541835051 5865
540901717 12003
540556231 640
539690077 458
536755469 17495
536541371 19139
533741647 800
533149049 19246
529455413 6822
529181777 16265
529181671 5890
528361837 5003
527867869 12933
527837467 9226
526697453 15635
525872857 7505
525047461 8119
524012941 8595
523774747 15906
523730429 16181
522588133 431
519914669 11800
519474727 16935
518656559 16102
518178527 16095
518115947 12471
517253899 19007
517220449 13913
516998177 5705
516634439 16071
515393273 2349
513522881 170
511882453 1577
511553501 1705
509751577 1731
506428253 5304
506201489 249
505623553 2004
504745877 15885
504509321 17541
503843357 14840
503623843 11167
503405849 11431
503374909 7295
500735659 629
500687189 15821
500578873 8318
497769133 6381
497477389 46
497168879 14141
497149277 15765
495695423 6567
495530033 16059
495393541 6280
495303269 21339
494258801 2549
493423247 4565
492781123 13839
491249783 10845
490992197 12341
490486859 15659
487876579 5333
487721257 56
487546459 12201
487067117 3265
486630211 6097
486129617 2381
484963513 10449
484934377 12977
484537517 4215
483508499 3257
483274423 6489
481886623 18411
480777953 21801
480489179 3519
480135343 19569
479638529 165
477950747 11699
477827071 5246
477604847 10449
476693807 13755
476631301 13439
476465993 6446
476298709 17979
475938377 15425
475930313 9947
474268667 3518
473227229 15381
471321287 1521
471286687 11914
470159101 10065
469767863 8229
469258547 14841
469092361 10091
468331301 5857
466884139 4360
466627279 13763
465359431 10091
464198773 8835
463910731 1949
462952907 7586
462941429 9065
462760471 7586
462562921 8055
462019001 6201
461685691 3732
460064551 8442
459666359 15159
459343397 10909
459335717 43
458212127 15135
457848929 15129
457241509 11525
456797167 15875
456397577 15105
456381763 11397
453080527 7605
451448093 11375
450996373 875
450580301 6672
449629799 11441
449024539 4809
448785811 13995
448174421 597
446791253 11645
445453201 5035
445181831 1705
444165677 10857
443497679 10449
440584769 14841
438630559 503
437720747 6609
437694823 4701
435349643 7175
435028229 13715
432900599 14711
432536563 148
432329089 10372
432071051 11055
432007721 4722
431927261 17291
431658949 971
430987793 8705
429413731 5068
429376859 14651
428486699 5957
425750789 14589
425683933 6114
425599973 4279
425004137 8627
424818803 12839
424523233 5379
424118249 14561
423233803 1229
422510399 1577
422372579 14531
421572601 10251
421501123 45
419830871 105
419068823 63
417579037 8613
417231907 5536
416841881 10935
416002589 14421
415896493 15425
415594537 9417
415490021 8770
414232127 6351
413578651 431
412135891 12249
411740863 4935
410551111 7295
410253689 14321
408728069 15272
406664927 272
406662097 2129
406360763 10485
405602741 9478
404431019 14219
404414891 13181
403635077 14205
402549223 10955
401932127 14175
401915273 636
401138299 2056
399942233 7042
397446901 429
396610763 1451
395760437 4531
395202023 4353
395156327 14055
394819049 14049
394068709 19581
393863383 9370
393784871 5301
393030179 10372
392574209 14009
392550497 1289
392468459 6371
389084833 9995
388371493 18491
388101001 3999
387481091 6671
387476911 18915
387462233 11240
387287167 11769
386545109 13901
386433899 13899
386096747 13203
385277153 16367
385100627 13875
384989453 878
384878639 13871
383651137 18209
382769767 15159
381428219 308
381268933 4924
381225077 13805
380180117 1971
379469411 6648
379185377 12399
378986891 2037
377900891 180
377806687 9717
377406083 721
376599131 1601
376361933 3669
376212359 4142
375212027 7594
374327101 10779
374309759 9125
373494487 14577
373186357 4257
370909243 5396
369888781 5238
369716027 13595
369389789 13589
367915963 3019
367326959 13551
367054333 18215
366566311 13298
365876089 5855
365702489 13521
365349067 2814
365018603 6843
364649189 3389
364372661 3819
363218627 13475
361258727 155
360888133 2849
360867889 4573
360772067 17921
360206219 13419
360143293 1577
358062179 13379
357821077 14637
357419981 90
357242309 13727
355689343 9065
354096871 12917
353855329 7667
353630813 11465
352666603 1955
351747853 1127
349479209 9197
349338527 13215
349173197 12657
348222431 2870
347608237 894
346910969 13169
345899797 9057
344596877 13125
344517889 17681
343482143 10863
343337909 13101
341962711 855
341283331 15641
340386811 7757
340129739 3998
340118281 12407
339931807 13679
338117009 13001
337944281 676
337825193 5957
337439033 10131
336918551 465
336640823 18255
336558539 12971
336247277 12965
335521559 12951
334845883 141
333349109 12909
332214503 4917
332098573 4155
331876849 1327
331710011 2352
330381523 803
330360659 12851
329798779 4263
329744039 12839
329558917 1049
328853869 971
328820189 12821
328717619 12819
327933071 10319
327180989 12789
326405383 4259
326143229 7319
325165261 16347
324192311 3355
323202599 12711
322543453 4131
322479331 1619
322035281 676
321070469 12669
320751727 2129
320158859 12651
319103621 8115
318036809 12609
318016967 6141
317736773 4701
317268781 13757
316631141 17181
313008133 8203
312356659 4722
312012689 12489
311469217 335
311114039 12471
309021137 7407
308045887 5097
306590803 785
305960159 9329
304940393 2169
304859777 12345
304662269 12341
304411769 9869
303782497 321
303736583 2056
303721903 5219
303330191 10655
302498587 4279
300137249 12249
299663311 8717
299648627 7425
299544247 11321
299497901 1269
298980119 12965
298589779 9711
298180409 12209
297985553 5430
297630247 4660
297497027 12195
297264119 1577
296061011 119
296049269 2249
295683457 9197
295330843 1421
295133893 5890
293824171 12141
293736857 17045
293574131 6261
293413199 12111
293390899 6009
293121749 1643
293090389 9437
293079037 4103
290796133 1595
290323769 12741
289743721 3396
289454021 9831
289205647 5705
288560971 3369
288324887 3006
287478409 8291
287373607 4673
287340377 11985
287339693 13728
286716277 16475
286280123 6315
285853367 4395
285561091 2546
285139139 11939
284840123 11345
284699407 4791
283228277 9279
283184819 4791
283066669 6269
280004279 11831
279141281 2232
278571583 6567
278428093 431
278089169 8291
277772351 2765
277606187 9417
277130563 5716
276736049 429
275295931 2448
275197529 11729
274541027 11715
273916931 1425
273891869 2819
273781831 10329
273101321 243
272519089 4431
271078133 3249
270085313 6501
267732019 3185
266934301 2271
266359853 5705
265780321 9341
265281953 803
265091201 7947
264735377 11135
264603509 11501
263573351 8745
263175611 5559
261351163 9489
261211519 10161
260823763 570
260560897 4269
260452823 8405
259463587 5502
258796177 69
257995523 135
257109967 1255
256296119 11319
255847441 1556
255407069 8037
255373483 1889
254898827 4515
254816363 2209
254758877 11285
254681717 1597
254388191 13116
254163913 2379
254127239 11271
253343263 9489
253157227 15231
251739203 7295
251695957 7539
250889599 14319
250712027 11195
250255139 14751
249960059 4157
249638339 11171
249279683 8891
248906873 9495
248542799 9313
247916003 370
247866503 4019
247764929 11129
247437269 132
246699391 3465
245809877 11085
245509559 2327
245399491 1092
244481327 11055
244039277 11045
244021013 3519
243299711 4601
243147493 277
242925169 7409
242763877 6687
242099009 11001
241765847 5105
241341181 1541
241031177 1386
240780539 10971
240120889 7175
240073877 4466
239305579 54
239203127 10935
237718109 10901
237290203 13145
237228899 10527
236993363 6565
236167201 842
235219861 8177
234652987 14841
234615013 10305
234266729 476
234233827 8781
233281817 1837
232714301 10091
232427579 10779
232126471 1108
231221759 10751
230436317 3149
229590601 10005
229171751 429
227748029 92
227407717 6141
226997773 6344
225735421 8693
224985077 10605
222503773 12712
222275717 1655
221948609 917
221014799 10511
219763039 905
219596269 279
219022117 6710
217730687 718
217469267 935
217108217 69
216064837 11055
213510779 10331
213482197 4795
213015119 10319
212900269 7838
211430179 1207
210989549 8223
209007343 6027
208988789 10221
208316183 5562
207595519 1751
207387443 8729
207350509 67
207164977 6351
206656181 1801
206575751 10007
206542649 10161
205931809 2406
205905691 9963
205818461 12509
205030181 2031
204810493 5867
204604381 9677
203838463 8967
203783443 6999
203707019 10091
203474273 2129
203166169 2592
203127517 2159
202235609 1121
201111179 9731
200933461 9713
200905123 6051
200398343 401
200228393 1092
200204101 11241
200114653 189
198510313 1451
196902089 9921
196665289 12495
196160267 8915
195801481 293
194734213 1481
192877199 6710
192611669 760
192497153 3861
192168209 9801
191998199 7685
191561309 272
191306579 9779
191215901 2841
190234687 1971
190064551 9207
190016023 5055
189926333 11615
189433379 9731
188860559 8421
188658089 4481
187473269 6201
187185643 9125
186720553 2675
186640859 9659
185591479 6261
185513753 2101
185483429 9629
185267113 13395
184508707 9101
184465207 8121
183626293 3299
183067723 5975
182406331 7757
182405281 3389
182257879 3819
181656367 4722
181461473 1784
181252303 6867
180906821 2355
180710713 125
179918723 2254
179827603 6071
179486173 4722
179468417 8829
178957631 4335
177859229 9429
177482219 9419
177355193 8099
177175919 824
176804609 9401
175866653 2546
175085653 3200
174331127 9335
174011603 6710
173850241 10709
173508347 981
173419243 7808
173209627 10667
173031037 6561
172916407 10889
172484399 444
172154447 2339
171065399 5855
170796419 4439
170247377 9225
170026019 9219
169323503 709
169131247 5079
168365761 9785
167987399 924
167765987 2132
167673827 9155
166880881 3185
166808729 10787
166576877 9125
166346227 161
164553359 12761
163990369 10319
163957369 3299
162575057 3257
162128069 11381
162011873 1362
161989757 2415
161844649 2249
161263807 1949
160930769 8969
160643849 8961
159365707 9039
158919073 4701
157247879 12477
156461803 1731
155999147 417
155964241 9131
155946629 8829
154757789 2001
154631987 7586
154567711 7586
153483959 8759
153469733 2675
152917747 10241
152702917 8251
152644127 8735
151838083 2675
151537739 321
151211743 1619
151110419 8691
151028693 8037
150554627 8675
150460747 2244
149349611 4782
148883513 96
148036151 5849
147791027 8595
147665491 8361
147241379 8579
147218849 1417
146624249 8561
146027747 515
145950377 2143
143873687 1299
143649853 1383
143089123 8370
142645429 6689
142525751 5259
142471163 709
142110257 4860
141868589 8421
141160423 5415
140896237 1421
140655589 1376
138961507 2765
138959021 671
138747097 545
138320027 8315
137456581 156
136768381 3033
135143861 6845
135025277 279
134816849 924
134717269 6856
134541047 572
134141321 5486
132529673 2307
132428053 1845
132190853 69
131747027 8115
131343893 4722
131000629 7101
130969019 8091
130824313 6111
130791313 10265
130625039 10161
130144463 1541
129774767 4722
129519491 2265
129156877 1751
128999177 275
128685737 1427
128363407 2853
128244667 610
127162067 2379
126794849 7961
126357347 173
125951621 1991
125273839 294
124799063 2675
123791069 6569
123080939 4781
123023167 4419
122939039 7839
122375189 7821
121862093 67
121797059 4701
121689511 4601
121638109 7565
121438319 7791
120918439 5105
120775579 2348
120242699 8251
120150263 7942
119730427 5121
119673769 9117
119488751 6027
119389877 7725
118535579 785
118214329 5655
117972479 7679
117954029 4687
117403381 417
117077557 78
116341163 1092
116134709 721
116032043 4389
114810649 5086
114687613 1108
114028349 1295
113891777 7545
113480833 6561
112997761 3899
112988027 7515
112847837 2944
112342561 7757
112230257 3465
112216649 9047
112095703 1235
112031191 6672
111202297 5271
110858281 1595
110162333 291
110084641 4656
110063543 905
110036363 7557
109437287 8251
109115779 6759
108052349 7349
107172119 7319
106999667 9065
106853533 5171
106767559 4295
106470527 7295
106418513 615
106270231 1996
105620363 4556
104934737 294
104771467 6381
104768791 5645
104668231 107
103856351 1803
103482233 1598
101913557 6999
101689309 5303
101375783 4722
101253049 1121
100849337 189
100697369 779
100571089 9731
100164677 4722
99794183 165
99276179 3401
98560039 261
98311327 4941
98060789 2915
98006999 6999
97857719 1531
97503629 6981
97428193 2814
97277057 8847
96874343 5567
96796649 8057
96656257 3569
95658421 2841
95590673 1655
94940843 171
94825261 6201
94750429 7205
94447099 8421
94192963 1575
94031489 1899
93717947 1541
93578039 6839
93415849 8805
92926381 9489
92707679 2970
92563637 7586
91592887 1731
91456049 6761
91444303 5670
90727993 5499
90646379 6731
90409357 2424
90332507 4472
89749453 8829
89079323 1815
88331857 6738
88227949 6316
88018643 5489
87164149 233
86778451 1869
86599379 6579
86372207 41
86132413 2339
85863959 6551
85811549 6549
85739441 3161
85474121 2331
85217491 2331
85077221 5045
83987279 6479
83592671 6671
82804457 8271
82373881 597
81824027 6395
81004093 2331
80841349 709
80800471 372
80702159 6351
80296127 6335
80043727 15
79973281 6059
79091249 1662
78881779 6827
78632069 6269
78535763 1739
78328541 37
78318113 75
78298673 1731
78281327 6255
78255283 1784
78170111 4529
78031277 6245
77912929 765
77513297 2951
76787027 6195
76785041 6567
76394699 1457
76146277 1516
75888763 5567
75858667 5207
75845599 144
75391759 1899
75324439 2607
75256963 69
75255119 1060
74162639 3019
73958579 1528
73867301 8511
73402907 43
73370639 5855
71670377 5985
71526779 5979
71227879 2412
71095889 8291
70784171 1335
70599761 5415
70522457 1421
68643073 7841
68453989 1809
68414933 2772
68271611 1617
68249473 1226
68162971 179
68049383 2055
67913311 878
67872289 2791
67719671 731
67445311 2697
67410773 783
67085269 5705
67053989 5789
66742399 1731
66011287 6617
65809127 5735
65801353 756
65675941 6561
65465363 2498
64866293 3941
64851547 2956
64818599 2999
64803419 5691
64563271 2735
64393669 1905
64223923 3455
63863081 4224
63850649 5649
63399253 783
63238319 1929
62812721 3219
62278379 5579
62047541 6261
61921813 4115
61747817 189
61673551 1092
61625813 3003
61614661 945
61512271 2169
61379779 301
61348303 346
61315937 1211
60951967 629
60917959 4701
60549509 5501
60194353 676
60114449 118
59847269 5469
59463121 439
59236169 5441
58944229 3599
58671527 5415
58635307 4323
58491193 1133
58361861 879
58035847 4389
57971131 395
57696271 1335
57561397 2265
57542983 7281
57305021 3353
57204223 519
57181097 1115
56720539 7017
56369959 6419
56192761 827
55521833 3975
55192061 44
55101283 2619
54972221 3911
54711029 5229
54609977 2207
54384493 5739
54261827 5837
54224923 3965
53747909 2231
53649191 200
53380277 5165
53251993 67
53161991 453
53091359 5151
52688347 5829
52270199 5111
52158661 681
52157761 6869
52147577 5105
52052893 63
51990157 43
51496283 3635
51436499 569
50939467 174
50931313 541
50748091 2990
50459303 43
50349331 165
50205139 2814
49378559 728
49327277 4965
47794339 692
47784307 1365
47452687 371
47394679 671
47050183 3257
46818029 15
46792091 939
46572193 401
46315499 4811
45836117 1731
45821767 69
45779849 2015
45009397 242
44808791 189
44762677 5250
44747047 41
44706773 2182
44561519 4719
44409923 3123
44222309 4701
44144069 1049
43945247 3733
43825841 4025
43786579 2613
43659839 4671
43469267 2263
43424039 1869
43416179 445
43219651 129
43137209 5921
43100969 4641
43043437 4901
42896779 4749
42693419 4619
42526591 3299
42361409 4601
42118579 4722
42117073 5477
41721271 3537
41578091 924
41378167 881
41275957 2547
41205163 5385
41190703 1257
40901489 4521
40886947 105
40880027 5781
40635109 267
40472743 569
40397983 2045
40229957 5681
40129619 2989
39995609 639
39916799 11
39823349 4461
39590021 5567
39439271 1235
39312047 1133
39199309 2878
38750659 1733
38589347 1586
38548589 4389
38440607 69
37971403 3299
37953677 4449
37763387 615
37539119 2211
37515113 28
37416109 1529
37395433 619
37147471 486
36874879 2271
36699599 3257
36687223 336
36165163 419
35834941 1092
35707949 231
35665757 2375
35553527 4215
35452409 4209
35354867 2692
34964653 572
34833763 1363
34781633 4077
34613129 2691
34248917 881
34231991 885
34150979 4131
34064011 2150
33788309 4109
33727987 2061
33400109 1731
33368141 924
33154489 1751
32592389 2263
32125901 3455
31992239 1557
31857479 2050
31680497 4155
31317919 2801
31234387 3012
31233343 2879
31152679 1595
30948427 2618
30933509 249
30713497 173
30548603 629
30441977 2990
30331583 5009
30228901 2399
29754523 1992
29648849 3849
29587277 3845
29407643 641
29238743 1092
29230699 879
29188619 3819
28923451 1403
28914209 3801
28904509 96
28789157 545
28762319 3791
28689629 689
28684697 519
28684339 221
28338181 536
28259963 551
28247701 1541
28123829 1705
27989383 2098
27883949 309
27774211 190
27769877 3725
27729313 1280
27617159 3945
27598603 5031
27562541 4799
27469957 3459
27450677 827
26736851 1092
26422007 3465
26162209 2620
26071181 702
26034677 3531
26010077 3605
25864919 881
25748213 1705
25674403 15
25526363 765
25180511 881
24905743 2334
24799679 721
24764953 109
24643709 3509
24626179 3915
24624049 242
24314761 4929
24225869 765
24215263 2263
23918399 1365
23891327 3455
23577269 3687
23444563 2651
23400781 1739
23364563 1863
23223413 892
22987589 3389
22902743 4347
22898411 56
22802737 4097
22407503 1705
22334827 999
22181129 3329
22103581 1049
21544603 150
21471013 4347
21362351 64
21196421 4505
20936221 2711
20902523 2990
20837447 3737
20738573 2963
20734139 105
20659031 3987
20467339 1927
20377801 967
20341369 1541
20241379 569
20175011 4347
20044711 639
19816477 819
19672127 3135
19593323 422
19411477 2081
19217257 52
19136107 2409
19130681 1169
19000529 3081
18966289 2399
18927709 615
18803777 3065
18559589 147
17909263 447
17844139 2375
17826203 1115
17738713 349
17644769 2969
17639903 210
17549849 2961
17347657 2661
17326753 915
17190493 580
16933933 849
16877911 1916
16816147 3489
16674479 2457
16646387 747
16459321 3879
16421143 185
16295131 3185
16156769 2841
16048829 250
15926903 569
15728099 697
15645919 1769
15638027 2795
15620629 1380
15598181 111
15596881 1547
15591131 96
15559741 249
15535241 1092
15304277 2765
15017939 2739
14738203 641
14608163 209
14471537 2835
14449789 2399
14175149 2661
14171593 1185
14169161 899
13991609 3525
13700917 401
13689527 2615
13666901 111
13607821 1859
13588063 521
13521181 2729
13418789 2589
13380359 939
13373117 18
13329193 837
13318303 1151
13299739 2239
13021837 629
13007549 2549
12804329 2529
12760541 2586
12758477 789
12703319 2519
12675643 1092
12636581 2027
12632611 1043
12522509 2501
12346909 939
12305011 721
12288217 1259
12263627 2475
12224039 2471
12206347 1787
12203797 3299
12164777 2465
11971237 1751
11956039 1995
11939281 575
11939129 2195
11881979 871
11870627 2435
11714471 63
11710351 2291
11678047 57
11584127 2546
11563967 2265
11543071 1043
11445719 2391
11395369 2351
11331179 2379
11328007 43
11293127 2375
11003449 249
10994453 43
10969187 1541
10953539 2339
10585037 21
10464031 825
10372717 2111
10210241 52
10172663 1739
10093327 168
9977029 301
9903521 1397
9832187 809
9707249 2445
9589339 1031
9577609 1169
9492467 1125
9477049 971
9144503 1783
9111941 1287
9075929 2129
9075751 1595
9018539 2555
8981443 2341
8974379 2295
8906309 2109
8718989 2675
8678717 2661
8654879 2079
8562443 878
8546399 267
8517739 1997
8427889 1446
8426401 445
8401229 905
8401091 173
8225449 2162
8211377 2025
8082209 2009
7919537 234
7787203 43
7779539 1971
7666441 2279
7651307 1665
7646591 1133
7588943 1667
7499929 857
7469719 863
7349653 361
7290197 2027
7154363 765
7135993 2027
6995669 1869
6957871 291
6921059 1859
6809399 1859
6789869 765
6781183 46
6768379 1323
6700861 939
6645277 2205
6615403 1829
6589859 1799
6526433 629
6388111 301
6384421 1655
6381377 1785
6308119 1233
6301991 1611
6295649 305
6183311 939
6178547 1191
6112097 567
6098777 1745
6041741 1521
6001379 1731
5822051 445
5792669 941
5701057 570
5630231 1565
5603797 1619
5552777 1665
5534801 249
5415089 276
5354627 1635
5289377 1625
5226761 557
5186693 844
5179087 2241
5041021 924
5038843 534
4950973 1707
4925203 809
4923617 111
4921069 419
4900039 64
4790803 1199
4783091 51
4730113 1705
4583291 276
4561709 1509
4540271 1308
4507271 1899
4417877 1485
4356917 723
4308427 1108
4283551 1871
4270339 615
4218059 1451
4207573 905
4118011 361
4116403 1705
4082083 39
4074397 242
4068377 1425
4045589 1421
4002211 1115
3979909 1043
3957469 69
3904301 1092
3829099 1665
3787891 581
3768691 1705
3733277 1365
3689047 1691
3682453 611
3655871 807
3648949 221
3628799 10
3609187 42
3588439 57
3570059 539
3502861 441
3470381 498
3351437 84
3309289 1445
3184067 401
3070523 11
3054127 276
3027029 1229
3020627 1577
3004069 131
2982493 1719
2962189 1037
2908537 65
2901149 193
2892187 55
2881199 1199
2872087 165
2845121 633
2812721 1487
2739343 1019
2738969 1169
2695529 44
2669041 599
2666203 281
2634323 505
2597069 84
2518889 1121
2494927 111
2426159 281
2415739 105
2398397 1199
2379409 1371
2377289 1089
2361661 575
2348047 11
2329781 67
2275381 737
2261261 749
2224543 765
2206049 1049
2194303 417
2179313 329
2140373 615
2123809 459
1961189 989
1952141 597
1883179 135
1877549 123
1861843 69
1845743 611
1837603 719
1818671 96
1780153 869
1768139 939
1757381 441
1742651 881
1735513 11
1704317 397
1683109 575
1682743 361
1642577 905
1621513 1179
1584839 767
1562831 375
1549679 879
1530041 567
1453351 95
1449059 165
1445471 96
1422919 125
1406813 827
1406299 276
1394339 813
1369237 67
1359227 291
1338511 437
1316057 881
1313009 809
1295627 1011
1293337 567
1281233 881
1278847 767
1269673 345
1244413 43
1206901 431
1192739 771
1163779 663
1131931 663
1101869 741
1094617 329
1089307 881
1065371 459
1060483 881
998771 342
980699 699
952013 135
942841 609
937103 276
935897 197
903113 57
891757 368
889159 82
865861 15
850859 651
829271 401
828827 321
828521 569
824969 641
819839 639
809849 64
800881 881
796457 323
794429 629
793157 276
779497 54
759527 615
756731 43
749699 611
748081 663
732857 767
732661 717
721453 465
719963 125
719309 591
687377 585
685309 399
683779 237
657997 617
645377 69
644681 335
605791 52
598337 67
598321 725
595759 755
568819 29
563833 84
541319 519
535981 43
533161 561
531721 429
528007 189
520199 43
518663 75
518569 142
505387 46
488857 431
484651 239
477709 272
472877 485
462877 431
460219 21
453457 465
448909 39
431741 191
423659 459
416327 455
398179 54
391169 441
390919 221
383233 407
382121 105
376591 179
370229 429
362879 9
361117 107
356393 525
346981 465
344051 267
329921 129
329653 69
326041 112
323287 189
315587 272
315071 507
266789 429
243407 272
234601 189
218129 329
205501 67
193777 105
192139 269
191959 122
189869 179
184507 54
180619 11
176879 71
168611 96
162923 189
153253 231
147053 153
138037 111
135143 25
133501 11
130313 75
129709 149
128417 279
125249 249
120389 129
118933 21
118229 189
107879 231
102089 11
99443 236
90949 96
90751 75
89801 67
88013 281
85651 43
83129 43
81803 177
77123 231
76189 44
74351 98
72389 189
69947 111
64979 179
64789 48
60023 90
58879 43
55739 69
55277 165
52777 67
50933 15
48827 155
47029 129
40319 8
37127 135
33431 99
32989 9
31877 125
28471 69
27931 15
25199 111
23999 101
23267 37
22577 105
18349 29
16517 81
16337 15
11449 105
10379 53
9869 69
9641 29
5083 11
3569 41
2627 35
2047 21
1829 29
1643 15
1387 17
961 15
901 15
527 15
391 11
299 11
221 11
121 9
119 5
61 59
60 1
59 57
58 1
57 1
56 1
55 1
54 1
53 51
52 1
51 1
50 1
49 1
48 1
47 45
46 1
45 1
44 1
43 41
42 1
41 39
40 1
39 1
38 1
37 35
36 1
35 1
34 1
33 1
32 1
31 29
30 1
29 27
28 1
27 1
26 1
25 1
24 1
23 21
22 1
21 1
20 1
19 17
18 1
17 15
16 1
15 1
14 1
13 11
12 1
11 9
10 1
9 1
8 1
7 5
6 1
5 3
4 1
3 1
2 1
1 0
)";
void init(int key, int value)
{
	stringstream convert;
	convert << TABLE;
	while (convert >> key >> value) table[key] = value;
}
int power(int a, int b, int p)
{
    if (b == 1) return a;
    int x = power(a, b >> 1, p);
    x = 1ll * x * x % p;
    if (b & 1) x = 1ll * x * a % p;
    return x;
}
bool check(int n, int h, int a)
{
	if (n % a == 0) return false;
	int now = power(a, h, n);
	if (now == 1) return true;
	while (h != n - 1)
	{
		if (now == n - 1) return true;
		now = 1ll * now * now % n;
		h <<= 1;
	}
	return false;
}
bool prime(int n)
{
	int h = n - 1;
	while ((h & 1) == 0) h >>= 1;
	if (!check(n, h, 2)) return false;
	if (!check(n, h, 7)) return false;
	if (!check(n, h, 61)) return false;
	return true;
}
int solve(int n)
{
	if (table.count(n)) return table[n];
	if (prime(n)) return n - 2;
	return 1;
}
int main()
{
	freopen("factorial.in", "r", stdin);
	freopen("factorial.out", "w", stdout);
	init(0, 0);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		scanf("%d", &n);
		printf("%d\n", solve(n));
	}
	return 0;
}
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 93ms
  4. Powered by Hydro v4.19.1 Community