#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
int dt[] = {
2,3,6,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432,1572864,3145728,6291456,12582912,25165824,50331648,100663296,201326592,402653184,805306368,-1,
3,4,12,36,108,324,972,2916,8748,26244,78732,236196,708588,2125764,6377292,19131876,57395628,172186884,516560652,-1,
5,5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625,-1,
7,8,56,392,2744,19208,134456,941192,6588344,46118408,322828856,-1,
11,10,110,1210,13310,146410,1610510,17715610,194871710,-1,
13,7,91,1183,15379,199927,2599051,33787663,439239619,-1,
17,9,153,2601,44217,751689,12778713,217238121,-1,
19,18,342,6498,123462,2345778,44569782,846825858,-1,
23,24,552,12696,292008,6716184,154472232,-1,
29,14,406,11774,341446,9901934,287156086,-1,
31,30,930,28830,893730,27705630,858874530,-1,
37,19,703,26011,962407,35609059,-1,
41,20,820,33620,1378420,56515220,-1,
43,44,1892,81356,3498308,150427244,-1,
47,16,752,35344,1661168,78074896,-1,
53,27,1431,75843,4019679,213042987,-1,
59,58,3422,201898,11911982,702806938,-1,
61,15,915,55815,3404715,207687615,-1,
67,68,4556,305252,20451884,-1,
71,70,4970,352870,25053770,-1,
73,37,2701,197173,14393629,-1,
79,78,6162,486798,38457042,-1,
83,84,6972,578676,48030108,-1,
89,11,979,87131,7754659,690164651,-1,
97,49,4753,461041,44720977,-1,
101,50,5050,510050,51515050,-1,
103,104,10712,1103336,113643608,-1,
107,36,3852,412164,44101548,-1,
109,27,2943,320787,34965783,-1,
113,19,2147,242611,27415043,-1,
127,128,16256,2064512,262193024,-1,
131,130,17030,2230930,292251830,-1,
137,69,9453,1295061,177423357,-1,
139,46,6394,888766,123538474,-1,
149,37,5513,821437,122394113,-1,
151,50,7550,1140050,172147550,-1,
157,79,12403,1947271,305721547,-1,
163,164,26732,4357316,710242508,-1,
167,168,28056,4685352,782453784,-1,
173,87,15051,2603823,450461379,-1,
179,178,31862,5703298,-1,
181,90,16290,2948490,533676690,-1,
191,190,36290,6931390,-1,
193,97,18721,3613153,697338529,-1,
197,99,19503,3842091,756891927,-1,
199,22,4378,871222,173373178,-1,
211,42,8862,1869882,394545102,-1,
223,224,49952,11139296,-1,
227,228,51756,11748612,-1,
229,114,26106,5978274,-1,
233,13,3029,705757,164441381,-1,
239,238,56882,13594798,-1,
241,120,28920,6969720,-1,
251,250,62750,15750250,-1,
257,129,33153,8520321,-1,
263,88,23144,6086872,-1,
269,67,18023,4848187,-1,
271,270,73170,19829070,-1,
277,139,38503,10665331,-1,
281,28,7868,2210908,621265148,-1,
283,284,80372,22745276,-1,
293,147,43071,12619803,-1,
307,44,13508,4146956,-1,
311,310,96410,29983510,-1,
313,157,49141,15381133,-1,
317,159,50403,15977751,-1,
331,110,36410,12051710,-1,
337,169,56953,19193161,-1,
347,116,40252,13967444,-1,
349,174,60726,21193374,-1,
353,59,20827,7351931,-1,
359,358,128522,46139398,-1,
367,368,135056,49565552,-1,
373,187,69751,26017123,-1,
379,378,143262,54296298,-1,
383,384,147072,56328576,-1,
389,97,37733,14678137,-1,
397,199,79003,31364191,-1,
401,100,40100,16080100,-1,
409,204,83436,34125324,-1,
419,418,175142,73384498,-1,
421,21,8841,3722061,-1,
431,430,185330,79877230,-1,
433,217,93961,40685113,-1,
439,438,192282,84411798,-1,
443,444,196692,87134556,-1,
449,224,100576,45158624,-1,
457,229,104653,47826421,-1,
461,46,21206,9775966,-1,
463,464,214832,99467216,-1,
467,468,218556,102065652,-1,
479,478,228962,109672798,-1,
487,488,237656,115738472,-1,
491,490,240590,118129690,-1,
499,498,248502,124002498,-1,
503,504,253512,127516536,-1,
509,254,129286,65806574,-1,
521,26,13546,7057466,-1,
523,524,274052,143329196,-1,
541,90,48690,26341290,-1,
547,548,299756,163966532,-1,
557,31,17267,9617719,-1,
563,188,105844,59590172,-1,
569,284,161596,91948124,-1,
571,570,325470,185843370,-1,
577,289,166753,96216481,-1,
587,588,345156,202606572,-1,
593,297,176121,104439753,-1,
599,598,358202,214562998,-1,
601,300,180300,108360300,-1,
607,608,369056,224016992,-1,
613,307,188191,115361083,-1,
617,309,190653,117632901,-1,
619,206,127514,78931166,-1,
631,630,397530,250841430,-1,
641,320,205120,131481920,-1,
643,644,414092,266261156,-1,
647,648,419256,271258632,-1,
653,327,213531,139435743,-1,
659,658,433622,285756898,-1,
661,55,36355,24030655,-1,
673,337,226801,152637073,-1,
677,113,76501,51791177,-1,
683,684,467172,319078476,-1,
691,138,95358,65892378,-1,
701,175,122675,85995175,-1,
709,118,83662,59316358,-1,
719,718,516242,371177998,-1,
727,728,529256,384769112,-1,
733,367,269011,197185063,-1,
739,738,545382,403037298,-1,
743,248,184264,136908152,-1,
751,750,563250,423000750,-1,
757,379,286903,217185571,-1,
761,95,72295,55016495,-1,
769,96,73824,56770656,-1,
773,387,299151,231243723,-1,
787,788,620156,488062772,-1,
797,57,45429,36206913,-1,
809,202,163418,132205162,-1,
811,270,218970,177584670,-1,
821,205,168305,138178405,-1,
823,824,678152,558119096,-1,
827,828,684756,566293212,-1,
829,69,57201,47419629,-1,
839,838,703082,589885798,-1,
853,427,364231,310689043,-1,
857,429,367653,315078621,-1,
859,78,67002,57554718,-1,
863,864,745632,643480416,-1,
877,439,385003,337647631,-1,
881,88,77528,68302168,-1,
883,884,780572,689245076,-1,
887,888,787656,698650872,-1,
907,908,823556,746965292,-1,
911,70,63770,58094470,-1,
919,102,93738,86145222,-1,
929,464,431056,400451024,-1,
937,469,439453,411767461,-1,
941,470,442270,416176070,-1,
947,948,897756,850174932,-1,
953,53,50509,48135077,-1,
967,88,85096,82287832,-1,
971,970,941870,914555770,-1,
977,163,159251,155588227,-1,
983,984,967272,950828376,-1,
991,198,196218,194452038,-1,
997,499,497503,496010491,-1,
-2
};
int main() {
int n, p;
cin >> n >> p;
int* pt = dt;
vector<long long> cnt(1001);
while ((*pt) >= 0) {
int ii = *pt;
pt ++;
long long res = 0;
while ((*pt) != -1) {
res += n / (*pt);
pt ++;
}
pt ++;
cnt[ii] = res;
}
for (int i=2; i<=p; i++) {
long long res = 99999999999LL;
int j = i;
for (int k=2; k<=j; k++) {
if (j % k == 0) {
int pw = 0;
while (j % k == 0) { j /= k; pw ++; }
res = min(res, cnt[k] / pw);
}
}
cout << res << endl;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1720 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1720 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1720 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1720 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
1720 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1720 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1720 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1720 KB |
Output is correct |
