#339091 (C) No.407 鴨等素数間隔列の数え上げ

• 問題: No.407 鴨等素数間隔列の数え上げ
• ユーザー: bal4u
• 提出日時: 2019-04-16 12:17:47
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 19 ms / 1,000 ms
• コード長: 12,287 bytes
• コンパイル時間: 337 ms
• コンパイル使用メモリ: 32,496 KB
• 実行使用メモリ: 6,804 KB
• 最終ジャッジ日時: 2023-10-22 06:58:50
• 合計ジャッジ時間: 1,724 ms
• ジャッジサーバーID （参考情報）: judge13 / judge10

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	1 ms; 4,348 KB
testcase_02	AC	1 ms; 4,348 KB
testcase_03	AC	16 ms; 6,804 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	6 ms; 6,804 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	1 ms; 4,348 KB
testcase_08	AC	1 ms; 4,348 KB
testcase_09	AC	6 ms; 6,804 KB
testcase_10	AC	1 ms; 4,348 KB
testcase_11	AC	1 ms; 4,348 KB
testcase_12	AC	1 ms; 4,348 KB
testcase_13	AC	1 ms; 4,348 KB
testcase_14	AC	8 ms; 6,804 KB
testcase_15	AC	2 ms; 4,348 KB
testcase_16	AC	6 ms; 6,804 KB
testcase_17	AC	1 ms; 4,348 KB
testcase_18	AC	5 ms; 6,804 KB
testcase_19	AC	17 ms; 6,804 KB
testcase_20	AC	19 ms; 6,804 KB
testcase_21	AC	1 ms; 4,348 KB
testcase_22	AC	1 ms; 4,348 KB
testcase_23	AC	7 ms; 6,804 KB
testcase_24	AC	1 ms; 4,348 KB
testcase_25	AC	19 ms; 6,804 KB
testcase_26	AC	1 ms; 4,348 KB
testcase_27	AC	1 ms; 4,348 KB
testcase_28	AC	1 ms; 4,348 KB
testcase_29	AC	5 ms; 6,804 KB
testcase_30	AC	1 ms; 4,348 KB
testcase_31	AC	7 ms; 6,804 KB
testcase_32	AC	19 ms; 6,804 KB
testcase_33	AC	18 ms; 6,804 KB
testcase_34	AC	19 ms; 6,804 KB
testcase_35	AC	19 ms; 6,804 KB

ソースコード

// yukicoder: No.406 鴨等間隔の法則
// 2019.4.16 bal4u

#include <stdio.h>
#include <math.h>

#define MAX  5000002
char notPrime[MAX + 2] = { 1,1,0,0,1 };			// zero: if prime 
void sieve(int max)
{
	int i, j, b;
	b = (int)sqrt((double)max);
	for (i = 3; i <= b; i += 2) {
		if (!notPrime[i]) {
			for (j = i * i; j < MAX; j += i) notPrime[j] = 1;
		}
	}
}

#define RANGE 10000
long long tbl[505][2] = { {0, 0},
{1228,5736394}, {2261,21171189}, {3244,45675862}, {4202,79170664},
{5132,121013306}, {6056,171848736}, {6934,228890416}, {7836,296488206}, {8712,370927312},
{9591,454396535}, {10452,544815054}, {11300,642361190}, {12158,749586244}, {13009,864482119},
{13847,986017445}, {14682,1115391664}, {15496,1249676488}, {16341,1397596537}, {17169,1550847683},
{17983,1709600811}, {18806,1878392366}, {19617,2052799923}, {20436,2237143102}, {21220,2421385276},
{22043,2623031149}, {22836,2825260460}, {23641,3038641893}, {24431,3255847669}, {25223,3481508699},
{25996,3709507112}, {26799,3954371769}, {27607,4208959127}, {28403,4467656213}, {29181,4728235703},
{29976,5002513512}, {30756,5279384844}, {31521,5558589577}, {32299,5850385909}, {33066,6145711712},
{33859,6458901529}, {34613,6764361103}, {35389,7086429797}, {36161,7414564287}, {36940,7753373170},
{37705,8093723583}, {38457,8435814137}, {39222,8791579374}, {40004,9162979208}, {40765,9532077299},
{41537,9914236193}, {42290,10294506868}, {43060,10691097202}, {43824,11092186116}, {44571,11491808989},
{45321,11900563181}, {46071,12316800851}, {46818,12738842358}, {47587,13180991083}, {48350,13627351484},
{49097,14071826343}, {49860,14533463862}, {50611,14995344483}, {51340,15450946376}, {52073,15916347209},
{52830,16404679970}, {53563,16884834921}, {54308,17380202288}, {55062,17889176420}, {55814,18404329914},
{56542,18910286310}, {57305,19448220645}, {58028,19965116920}, {58788,20516088662}, {59530,21061503170},
{60237,21588259023}, {60977,22146949833}, {61732,22724500916}, {62467,23294120341}, {63205,23873433067},
{63950,24465663436}, {64682,25054895046}, {65415,25652285581}, {66160,26266844424}, {66889,26875509717},
{67616,27489818804}, {68341,28109692653}, {69094,28761037052}, {69822,29398075550}, {70554,30045873872},
{71273,30689332263}, {72025,31369995681}, {72733,32017875925}, {73473,32702363907}, {74186,33369015916},
{74906,34049359800}, {75617,34728329601}, {76349,35434672611}, {77066,36133654012}, {77776,36833009472},
{78497,37550402021}, {79250,38307175232}, {79969,39036979343}, {80701,39787246769}, {81402,40512751710},
{82133,41276629125}, {82831,42013066533}, {83547,42775656981}, {84269,43551818387}, {84975,44317727437},
{85713,45125753693}, {86449,45939043061}, {87165,46737288747}, {87883,47545060013}, {88601,48359954121},
{89301,49161463645}, {90029,50002290949}, {90763,50857322923}, {91489,51710417935}, {92224,52581367530},
{92937,53433406129}, {93613,54247978153}, {94357,55151942211}, {95050,56000935130}, {95744,56858064010},
{96468,57759511222}, {97181,58654399057}, {97899,59562673235}, {98609,60467892783}, {99331,61395716183},
{100020,62287995770}, {100729,63213221261}, {101432,64137644484}, {102145,65082300453}, {102851,66024839999},
{103543,66955471631}, {104257,67922898251}, {104966,68890666706}, {105689,69884867901}, {106384,70847450774},
{107125,71881256645}, {107804,72835297770}, {108486,73800261878}, {109204,74823439624}, {109927,75860935735},
{110629,76875349477}, {111330,77895250782}, {112046,78944124462}, {112751,79984094035}, {113457,81032532937},
{114154,82074443254}, {114885,83174552715}, {115587,84238036221}, {116278,85291831550}, {116964,86344912342},
{117662,87423357962}, {118375,88532117557}, {119056,89597890448}, {119757,90701913605}, {120450,91800358762},
{121126,92878592186}, {121845,94032481433}, {122539,95153302905}, {123249,96307074511}, {123941,97438402703},
{124633,98576757975}, {125334,99736854912}, {126050,100929095376}, {126752,102105030430}, {127427,103242387749},
{128140,104450958702}, {128836,105637642134}, {129521,106812427039}, {130212,108004427026}, {130901,109199917323},
{131607,110431974855}, {132291,111632300729}, {132970,112830807268}, {133670,114073320386}, {134358,115301312590},
{135071,116581137845}, {135775,117851921689}, {136447,119071568441}, {137165,120381909889}, {137840,121620451716},
{138541,122913801663}, {139248,124225299762}, {139951,125536370799}, {140640,126828232636}, {141337,128142060783},
{142028,129451433480}, {142717,130764039557}, {143413,132096820083}, {144124,133465548884}, {144809,134791081475},
{145501,136136977175}, {146185,137474175075}, {146858,138796554296}, {147528,140119853674}, {148218,141489414870},
{148932,142913828920}, {149637,144327406493}, {150327,145717765397}, {151020,147121099848}, {151710,148525232918},
{152381,149897385937}, {153077,151327709761}, {153771,152760859961}, {154444,154157377456}, {155130,155587733704},
{155804,156999759088}, {156503,158471116895}, {157186,159915649010}, {157883,161396844759}, {158556,162833730070},
{159249,164320146627}, {159961,165854577431}, {160628,167298642258}, {161318,168799373802}, {161997,170283021419},
{162661,171740398595}, {163362,173286138414}, {164022,174747995306}, {164717,176294429247}, {165397,177814211635},
{166080,179347555626}, {166768,180899065884}, {167469,182486829961}, {168163,184065574547}, {168825,185578301631},
{169510,187150390018}, {170200,188740844660}, {170862,190273400906}, {171534,191835856658}, {172205,193402646833},
{172872,194966694834}, {173562,196591659714}, {174253,198225885763}, {174915,199798140173}, {175620,201479578708},
{176301,203110644371}, {176961,204697936469}, {177653,206369146569}, {178325,207998730139}, {178982,209598483974},
{179683,211312414613}, {180370,212999039432}, {181038,214645613464}, {181710,216308794360}, {182397,218016021091},
{183071,219697708193}, {183747,221391071189}, {184422,223088646492}, {185119,224848583881}, {185791,226552054205},
{186461,228257241323}, {187133,229974210047}, {187811,231713234103}, {188510,233513149116}, {189203,235304510773},
{189879,237058773599}, {190532,238759857916}, {191213,240540618951}, {191885,242304623831}, {192566,244098978642},
{193255,245921375955}, {193950,247766614888}, {194612,249530836804}, {195277,251309795385}, {195958,253138317634},
{196644,254987085882}, {197323,256823807179}, {198018,258710786800}, {198663,260468459323}, {199320,262265360936},
{199992,264109919010}, {200663,265958531443}, {201348,267852513842}, {202014,269700656886}, {202677,271547053849},
{203361,273458891713}, {204051,275394381825}, {204746,277350769856}, {205413,279234986387}, {206117,281230805481},
{206788,283139850040}, {207442,285006986776}, {208115,286935084861}, {208768,288812427414}, {209446,290768444866},
{210108,292684958372}, {210789,294663286913}, {211452,296595987708}, {212123,298558620103}, {212803,300554476085},
{213452,302465859298}, {214104,304392467168}, {214798,306450148766}, {215457,308410691391}, {216128,310413497778},
{216815,312471072263}, {217485,314484412015}, {218144,316471223350}, {218807,318476761555}, {219464,320470709142},
{220135,322513849671}, {220792,324520973184}, {221456,326556144108}, {222151,328693223505}, {222837,330809580765},
{223491,332833640337}, {224167,334932681313}, {224844,337041587392}, {225510,339122860876}, {226176,341210777884},
{226834,343280247428}, {227511,345416120935}, {228179,347530369337}, {228842,349635301708}, {229533,351836156573},
{230208,353992813412}, {230894,356191388908}, {231568,358358249162}, {232240,360525441686}, {232927,362747913057},
{233576,364853955188}, {234238,367008768698}, {234915,369219134093}, {235581,371400281195}, {236251,373601253351},
{236899,375736342229}, {237572,377960682220}, {238232,380148556614}, {238909,382399618815}, {239554,384550763340},
{240229,386808600813}, {240852,388898719270}, {241540,391213899630}, {242207,393465050425}, {242876,395729648494},
{243538,397977139118}, {244215,400282292893}, {244881,402556594319}, {245553,404858175151}, {246238,407211199514},
{246908,409519353578}, {247554,411751250114}, {248208,414017402208}, {248845,416230966331}, {249481,418447415489},
{250149,420782056779}, {250800,423063851578}, {251463,425394272411}, {252093,427615015631}, {252756,429958648536},
{253411,432280637141}, {254079,434655434417}, {254749,437044043415}, {255389,439332020573}, {256056,441723179790},
{256725,444128260161}, {257417,446622971393}, {258087,449044984945}, {258773,451531707201}, {259425,453901726847},
{260063,456227195827}, {260713,458603010947}, {261375,461029271431}, {262077,463609198607}, {262715,465960290649},
{263396,468476582950}, {264051,470903326797}, {264722,473396155798}, {265409,475955313733}, {266067,478412919877},
{266716,480843495728}, {267383,483348018297}, {268015,485727595823}, {268670,488200274032}, {269329,490694569445},
{269986,493187952848}, {270642,495684022880}, {271324,498285816594}, {271998,500863849642}, {272644,503341273528},
{273321,505944316357}, {273971,508450118011}, {274617,510946885327}, {275268,513469528244}, {275929,516037505633},
{276610,518689939918}, {277261,521232198657}, {277919,523808279387}, {278594,526457723238}, {279242,529007619546},
{279920,531682316040}, {280563,534225380181}, {281201,536755102791}, {281869,539410380853}, {282503,541936864523},
{283145,544501644259}, {283805,547144926769}, {284463,549786750863}, {285131,552475436129}, {285808,555207138826},
{286489,557961747891}, {287132,560569129414}, {287785,563223579819}, {288455,565953844897}, {289108,568621365098},
{289773,571344516341}, {290436,574066225976}, {291064,576650415916}, {291716,579339928458}, {292348,581953321640},
{293009,584693196537}, {293671,587443798745}, {294342,590238403238}, {294993,592956369183}, {295666,595772903134},
{296313,598487027811}, {296983,601304350063}, {297627,604018781441}, {298290,606819902238}, {298918,609479465308},
{299582,612298118390}, {300242,615106353784}, {300886,617852954998}, {301542,620657328454}, {302174,623365435754},
{302823,626152906523}, {303485,629002776743}, {304151,631876630481}, {304792,634649068196}, {305448,637492887946},
{306083,640251966747}, {306723,643039133261}, {307376,645889463930}, {308037,648781273863}, {308699,651684101047},
{309334,654474931930}, {309975,657298501885}, {310654,660296284262}, {311337,663318596819}, {311993,666228037955},
{312665,669215051745}, {313320,672133077942}, {313980,675079985628}, {314626,677970845128}, {315309,681034104231},
{315947,683901919557}, {316600,686843627982}, {317238,689724236830}, {317884,692647431508}, {318515,695509027495},
{319163,698454128773}, {319822,701455802406}, {320495,704528040289}, {321145,707501891301}, {321785,710436285201},
{322440,713445920554}, {323102,716494466158}, {323758,719521918188}, {324403,722505066015}, {325054,725522485480},
{325705,728546440791}, {326321,731413933199}, {326986,734516156846}, {327652,737629753782}, {328319,740754629567},
{328963,743778235403}, {329615,746845846437}, {330268,749924791660}, {330911,752962953359}, {331574,756102153392},
{332218,759157891568}, {332860,762210648918}, {333515,765331720301}, {334143,768330436293}, {334800,771474159582},
{335438,774533452862}, {336095,777690271805}, {336750,780844143802}, {337381,783888697601}, {338059,787166873551},
{338693,790238649867}, {339338,793370075946}, {340007,796624764265}, {340643,799725258475}, {341312,802993312680},
{341991,806316986091}, {342642,809510088782}, {343276,812626213776}, {343929,815842184881}, {344584,819074602964},
{345234,822288858552}, {345874,825459979508}, {346557,828851008725}, {347218,832139611488}, {347871,835394918645},
{348512,838596693106}};

#if 1
int main()
{
	int i, k, N, L, max;
	long long ans, s;

	scanf("%d%d", &N, &L);
	max = L / (N - 1);
	sieve(max);
	ans = 0, N--, L++;
	if (2 <= max) ans = L - (N << 1);
	k = (int)tbl[max/RANGE][0], s = tbl[max/RANGE][1];
	for (i = max/RANGE*RANGE+1; i <= max; i += 2)
		if (!notPrime[i]) k++, s += i;
	if (k) ans += (long long)k*L - (long long)N*s;
	printf("%lld\n", ans);
	return 0;
}
#else
int main()
{
	int i, k, sz;
	long long s;

	sieve(MAX);
	printf("int tbl[502][2] = {\n");
	sz = 1;
	k = 0, s = 0;
	for (i = 3; i <= MAX; i += 2) {
		if (i % RANGE == 1) {
			printf("{%d,%lld}, ", k, s);
			sz++;
			if (sz % 5 == 0) printf("\n");
		}
		if (!notPrime[i]) k++, s += i;
	}
	printf("};\n");
	printf("sz=%d\n", sz);
	return 0;
}
#endif