fork(1) download
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdint.h>
  4. #include <inttypes.h>
  5.  
  6. #define gc getchar_unlocked
  7. #define pc putchar_unlocked
  8.  
  9. void scanu(uint* n) {
  10. *n = 0;
  11. int ch = gc();
  12. while (ch < '0' || ch > '9') {
  13. ch = gc();
  14. }
  15. while (ch >= '0' && ch <= '9') {
  16. *n = (*n << 3) + (*n << 1) + (ch - '0');
  17. ch = gc();
  18. }
  19. }
  20.  
  21. //Big Endian
  22. typedef struct {
  23. uint length;
  24. uint64_t* digsets;
  25. } BigInt;
  26.  
  27. #define N 100
  28. #define D 1000
  29. #define BASE 100000000000000000
  30. BigInt* facts[N + 1];
  31. uint nf = 0;
  32.  
  33. BigInt* newBigInt(uint length, uint val) {
  34. BigInt* res;
  35. if ((res = malloc(sizeof(BigInt))) == NULL)
  36. return NULL;
  37. res->length = length;
  38. if ((res->digsets = malloc(sizeof(uint64_t) * length)) == NULL)
  39. return NULL;
  40. res->digsets[0] = val;
  41. uint i;
  42. for (i = 1; i < res->length; ++i) {
  43. res->digsets[i] = 0;
  44. }
  45. return res;
  46. }
  47.  
  48. void print(BigInt* f) {
  49. char buffer[D];
  50. uint i = f->length;
  51. while (i > 0 && !f->digsets[--i]) {
  52. }
  53. uint b=sprintf(buffer,"%lu", f->digsets[i]);
  54.  
  55. while (i--) {
  56. //previously
  57. //b+=sprintf( (buffer+b),"%017lu", f->digsets[i]);
  58. b+=sprintf( (buffer+b),"%017" PRIu64, f->digsets[i]);
  59. }
  60. for (i = 0; i < b; ++i) {
  61. pc(buffer[i]);
  62. }
  63. pc('\n');
  64. }
  65.  
  66. BigInt* multiply(BigInt* f, uint n) {
  67. uint i;
  68. BigInt* r = newBigInt(f->length + 1, 0);
  69. for (i = 0; i < f->length; ++i) {
  70.  
  71. r->digsets[i] += f->digsets[i] * n;
  72. if (r->digsets[i] > BASE) {
  73. r->digsets[i + 1] = r->digsets[i] / BASE;
  74. r->digsets[i] -= r->digsets[i + 1] * BASE;
  75. }
  76. }
  77. if (!r->digsets[r->length - 1]) {
  78. r->length--;
  79. }
  80. return r;
  81. }
  82.  
  83. BigInt* factorial(uint n) {
  84. uint i;
  85. for (i = nf; i <= n; ++i) {
  86. facts[i] = multiply(facts[i - 1], i);
  87. }
  88. return facts[n];
  89. }
  90.  
  91. int main(void) {
  92. uint t;
  93. scanu(&t);
  94. facts[0] = newBigInt(1, 1);
  95. facts[1] = facts[0];
  96. nf = 2;
  97. while (t--) {
  98. uint n;
  99. scanu(&n);
  100. print(factorial(n));
  101. }
  102. return EXIT_SUCCESS;
  103. }
  104.  
  105.  
Success #stdin #stdout 0s 2692KB
stdin
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
stdout
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
1932053504
1278945280
2004310016
2004189184
4006445056
3396534272
121645100408832000
2432902008176640000
51090942171709440000
1124000727777607680000
25852016738884976640000
620448401733239439360000
15511210043330985984000000
403291461126605635584000000
151451210418352160768000000
375163325313860501504000000
142318194101954543616000000
404075256658636308480000000
70927798017725562880000000
263130836933693530167218012160000000
8683317618811886495518194401280000000
295232799039604140847618609643520000000
10333147966386144929666651337523200000000
371993326789901217467999448150835200000000
13763753091226345046315979581580902400000000
7626541946601111760007224100074291200000000
39737098157443358640281739902897356800000000
346026777734345611269596115894272000000000
14187097887108170062053440751665152000000000
1405006117752879898543142606244511569936384000000000
60415263063373835637355132068513997507264512000000000
2658271574788448768043625811014615890319638528000000000
119622220865480194561963161495657715064383733760000000000
5502622159812088949850305428800254892961651752960000000000
258623241511168180642964355153611979969197632389120000000000
3823981000536072670862289047373375038521486354677760000000000
2691475298267560872252163321295376887552831379210240000000000
1429778737378043612608166064768844377641568960512000000000000
4199238870280224243016469303211063259720016986112000000000000
3612056454571660636856403766975289505440883277824000000000000
4274883284060025564298013753389399649690343788366813724672000000000000
230843697339241380472092742683027581083278564571807941132288000000000000
12696403353658275925965100847566516959580321051449436762275840000000000000
710998587804863451854045647463724949736497978881168458687447040000000000000
40526919504877216755680601905432322134980384796226602145184481280000000000000
203077683282878571829474910515074683828862318181142924420699914240000000000000
385171614489835737939019720389406345902876772687432540821294940160000000000000
346970200590144276341183223364380754172606361245952449277696409600000000000000
119842485598800856812176625227226004528988036003099405939480985600000000000000
31469973260387937525653122354950764088012280797258232192163168247821107200000000000000
1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000
126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000
8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000
544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000
36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000
31904183716830599600990418569171581047399201355367672371710738018221445712183296000000000000000
10955355501311372468338881272839092270544893520369393648040923257279754140647424000000000000000
36730444771796072783721689098736458938142546425857555362864628009582789845319680000000000000000
30881201197521167644239926010288584608120796235886430763388588680378079017697280000000000000000
61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000
4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000
330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000
24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000
1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000
3449171260285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000
2747385950297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000
2295125273528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000
3221395450294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000
5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000
475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000
39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000
3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000
281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000
175278526072732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000
216846232327717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000
184612342439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000
16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000
1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000
12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000
1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000
22837269745674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000
22056977839059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000
12935897509689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000
9241542599853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000
9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000