#283571 (C++14) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	FF256grhy
提出日時	2018-09-07 22:42:02
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,018 ms / 3,000 ms
コード長	14,223 bytes
コンパイル時間	1,572 ms
コンパイル使用メモリ	170,572 KB
実行使用メモリ	276,992 KB
最終ジャッジ日時	2024-11-29 16:44:57
合計ジャッジ時間	23,378 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	12 ms 10,496 KB
testcase_01	AC	12 ms 10,496 KB
testcase_02	AC	12 ms 10,496 KB
testcase_03	AC	14 ms 10,496 KB
testcase_04	AC	12 ms 10,496 KB
testcase_05	AC	12 ms 10,496 KB
testcase_06	AC	12 ms 10,496 KB
testcase_07	AC	12 ms 10,496 KB
testcase_08	AC	12 ms 10,496 KB
testcase_09	AC	12 ms 10,496 KB
testcase_10	AC	13 ms 10,496 KB
testcase_11	AC	13 ms 10,624 KB
testcase_12	AC	12 ms 10,496 KB
testcase_13	AC	12 ms 10,496 KB
testcase_14	AC	12 ms 10,496 KB
testcase_15	AC	12 ms 10,368 KB
testcase_16	AC	12 ms 10,624 KB
testcase_17	AC	13 ms 10,496 KB
testcase_18	AC	12 ms 10,368 KB
testcase_19	AC	13 ms 10,496 KB
testcase_20	AC	12 ms 10,624 KB
testcase_21	AC	15 ms 11,008 KB
testcase_22	AC	14 ms 10,752 KB
testcase_23	AC	12 ms 10,496 KB
testcase_24	AC	12 ms 10,368 KB
testcase_25	AC	17 ms 11,776 KB
testcase_26	AC	15 ms 11,392 KB
testcase_27	AC	12 ms 10,624 KB
testcase_28	AC	13 ms 10,624 KB
testcase_29	AC	13 ms 10,752 KB
testcase_30	AC	14 ms 10,752 KB
testcase_31	AC	14 ms 11,008 KB
testcase_32	AC	16 ms 11,520 KB
testcase_33	AC	17 ms 11,520 KB
testcase_34	AC	16 ms 11,264 KB
testcase_35	AC	14 ms 11,136 KB
testcase_36	AC	15 ms 11,136 KB
testcase_37	AC	13 ms 10,624 KB
testcase_38	AC	12 ms 10,624 KB
testcase_39	AC	16 ms 11,136 KB
testcase_40	AC	15 ms 11,136 KB
testcase_41	AC	15 ms 11,008 KB
testcase_42	AC	16 ms 11,008 KB
testcase_43	AC	14 ms 11,008 KB
testcase_44	AC	14 ms 10,880 KB
testcase_45	AC	13 ms 10,752 KB
testcase_46	AC	13 ms 10,624 KB
testcase_47	AC	13 ms 10,752 KB
testcase_48	AC	20 ms 11,904 KB
testcase_49	AC	20 ms 11,904 KB
testcase_50	AC	14 ms 11,008 KB
testcase_51	AC	15 ms 10,880 KB
testcase_52	AC	13 ms 10,752 KB
testcase_53	AC	34 ms 14,976 KB
testcase_54	AC	606 ms 99,328 KB
testcase_55	AC	572 ms 99,456 KB
testcase_56	AC	575 ms 99,328 KB
testcase_57	AC	91 ms 26,240 KB
testcase_58	AC	92 ms 26,112 KB
testcase_59	AC	36 ms 15,488 KB
testcase_60	AC	147 ms 34,432 KB
testcase_61	AC	144 ms 34,432 KB
testcase_62	AC	814 ms 127,360 KB
testcase_63	AC	307 ms 58,880 KB
testcase_64	AC	197 ms 42,112 KB
testcase_65	AC	202 ms 41,984 KB
testcase_66	AC	12 ms 10,496 KB
testcase_67	AC	12 ms 10,496 KB
testcase_68	AC	689 ms 111,872 KB
testcase_69	AC	688 ms 111,872 KB
testcase_70	AC	605 ms 100,864 KB
testcase_71	AC	612 ms 100,736 KB
testcase_72	AC	279 ms 55,168 KB
testcase_73	AC	1,374 ms 200,704 KB
testcase_74	AC	1,354 ms 200,704 KB
testcase_75	AC	19 ms 11,776 KB
testcase_76	AC	658 ms 109,312 KB
testcase_77	AC	104 ms 27,648 KB
testcase_78	AC	1,019 ms 156,288 KB
testcase_79	AC	685 ms 113,408 KB
testcase_80	AC	909 ms 140,544 KB
testcase_81	AC	594 ms 101,632 KB
testcase_82	AC	14 ms 10,624 KB
testcase_83	AC	93 ms 26,880 KB
testcase_84	AC	106 ms 28,928 KB
testcase_85	AC	508 ms 87,168 KB
testcase_86	AC	945 ms 143,872 KB
testcase_87	AC	2,018 ms 276,992 KB
testcase_88	AC	1,899 ms 276,096 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL memo[] = {
0, 891, 5605, 13426, 26405, 46662, 69399, 103218, 140317, 188442, 241580, 313868, 376379, 465520, 538803, 666282, 766912, 906785, 1030459, 1163809, 1320155, 1503243, 1643939, 1870681, 2116086, 2291311, 2494383, 2790025, 3086180, 3355683, 3613638, 3912101, 4172487, 4470969, 4902385, 5233821, 5677354, 6110983, 6528735, 6928795, 7343500, 7934265, 8304109, 8987313, 9388213, 9892389, 10467271, 11061536, 11676149, 12097726, 12916414, 13592300, 14235571, 14835446, 15447773, 16276068, 17130522, 17945529, 18643166, 19794972, 20312885, 21224825, 22082729, 23125855, 24371852, 25051758, 26005876, 26897146, 27988109, 29109650, 30356827, 31240205, 32238919, 33366493, 34308338, 35481768, 37119630, 38469335, 39620482, 40787646, 41980431, 43313078, 44553175, 46327900, 47495276, 48547134, 50151725, 51925306, 53463420, 55313522, 56617867, 58244197, 60051993, 61735447, 63453105, 65839740, 66971232, 69118549, 70967543, 73021429, 74588542, 76532478, 78689043, 80514328, 82746006, 84632960, 86167266, 88501311, 90674612, 92682576, 94719783, 96784698, 99090585, 101214941, 103370000, 105775548, 107771141, 109563637, 111604837, 114366761, 117404074, 119540702, 122179016, 125100490, 127325730, 130583994, 133645482, 136743251, 139368104, 141753782, 144974545, 147969877, 151284243, 153801877, 156633241, 159784840, 162109636, 165625557, 169186810, 171894991, 175244216, 178323659, 180819637, 183021156, 185871393, 189722382, 193622597, 196904553, 201570537, 205622737, 208354951, 211465845, 215643826, 219884722, 224190906, 228170499, 231095967, 235909584, 240398630, 243812055, 247648188, 252288487, 255807992, 258967218, 262549326, 267372669, 270216129, 275542808, 278444820, 282191610, 287254590, 291948303, 295821269, 299737504, 304999386, 310768725, 315250178, 318862413, 323423473, 327097389, 333594494, 338290435, 343502992, 348772623, 354094568, 359472728, 364408956, 367385829, 372890847, 375404986, 379458396, 385074101, 388671118, 394390025, 399098865, 407575453, 413463585, 417243323, 422679447, 428163164, 434797044, 439825248, 447151856, 452262170, 459148403, 463774885, 469608287, 473709862, 480811793, 486178507, 491583123, 498244844, 506196913, 510515265, 517343043, 523600924, 531808949, 537544504, 544611683, 551723436, 556942703, 565486940, 573455995, 579472113, 585527800, 590944209, 597083921, 605323879, 612944564, 618518185, 624832325, 636174467, 641906930, 649116455, 655624235, 660004173, 668822637, 677700832, 684423057, 694203827, 701030515, 710971871, 720225970, 725651606, 731891611, 739743429, 746059743, 753202376, 759614589, 766053239, 774953825, 781466502, 790495518, 796273876, 806236465, 814601032, 821324788, 831503643, 840035716, 846906558, 857282324, 864245848, 873877418, 883589078, 892468713, 901416654, 908601024, 917631354, 927639632, 938644079, 947874919, 957188393, 964668601, 974096894, 978843226, 988338479, 995970955, 1004611874, 1018156606, 1026921238, 1037721451, 1048588835, 1055529325, 1064504946, 1071533381, 1082614989, 1094816160, 1109144266, 1119474866, 1128821740, 1137157918, 1146588190, 1158192418, 1168794903, 1180534393, 1190198478, 1200991403, 1209679418, 1217287854, 1228241263, 1235959739, 1245893602, 1259254757, 1269335894, 1279471070, 1289648132, 1299885060, 1310178317, 1319374824, 1334380512, 1343668934, 1355348231, 1369448101, 1382455979, 1396750166, 1401531555, 1413535031, 1425618314, 1437742986, 1446279492, 1453628852, 1469618856, 1480756474, 1491962731, 1508230022, 1522095657, 1536045519, 1547508453, 1560334174, 1570634958, 1587457743, 1600490476, 1613558046, 1621469818, 1637323144, 1650636200, 1666670340, 1680126275, 1696370546, 1709968175, 1720919414, 1729146277, 1741574081, 1756820559, 1772136430, 1786128181, 1800225419, 1815786629, 1828576858, 1842878286, 1852923245, 1867345813, 1880356288, 1893465713, 1906621401, 1919880339, 1939090618, 1945040581, 1955439775, 1973394931, 1988408217, 2003553711, 2015681071, 2030904879, 2044704145, 2058565688, 2075583452, 2091130054, 2109866128, 2123981776, 2141379201, 2157239996, 2169992184, 2181193562, 2200478239, 2213406494, 2237759604, 2254088834, 2262285737, 2278724480, 2293612587, 2303563738, 2318550021, 2335249703, 2352037692, 2362148102, 2373971194, 2394324817, 2413116257, 2428555963, 2445801320, 2459638534, 2480489917, 2496188787, 2517243860, 2529564230, 2545433531, 2559652337, 2579253642, 2600766306, 2615151520, 2631441108, 2651417136, 2665993520, 2675149789, 2693503085, 2711945470, 2724920685, 2737891317, 2762131416, 2777115622, 2794044702, 2814818171, 2839515170, 2854759751, 2868158252, 2887339073, 2912420654, 2925981638, 2947375745, 2970852465, 2990493737, 3010238566, 3030017416, 3049951800, 3079995182, 3094065339, 3112219603, 3138584860, 3154851341, 3175287654, 3193754989, 3208179013, 3224733849, 3239225658, 3257924161, 3274648254, 3295595088, 3318760275, 3329315542, 3352616082, 3373911258, 3395244268, 3423146303, 3436075043, 3449038805, 3472857612, 3496822045, 3518655078, 3538419616, 3560468775, 3573756894, 3598151029, 3613741614, 3636094086, 3654071774, 3676573688, 3696937394, 3712816282, 3737842462, 3753794581, 3774419254, 3797423567, 3813596488, 3834445494, 3857691187, 3878678159, 3904413691, 3923210468, 3949162037, 3963365862, 3979991229, 4003791947, 4025326692, 4049279985, 4068556285, 4097584624, 4119410615, 4146235747, 4165806930, 4192782066, 4210026887, 4234741510, 4252061637, 4271932384, 4301844002, 4324390307, 4347022187, 4372258422, 4400131322, 4415378819, 4440882988, 4471538349, 4494683962, 4517888546, 4546331739, 4567105291, 4593200363, 4616743005, 4642997506, 4669349592, 4695780320, 4722286955, 4746249353, 4772994242, 4791725417, 4824033929, 4837532323, 4859160877, 4883593448, 4908078674, 4927184667, 4954589932, 4979341251, 5001386427, 5040097415, 5070649314, 5098583515, 5120967966, 5151845464, 5177220130, 5199885547, 5228259508, 5253883292, 5279568876, 5291020714, 5325460776, 5348495045, 5374476260, 5400574429, 5432588147, 5458860121, 5491072835, 5517526853, 5538165405, 5561823734, 5588509465, 5624196337, 5648074004, 5680991739, 5705013806, 5729139177, 5756381495, 5774561040, 5801891331, 5841531467, 5875244145, 5902911610, 5933761818, 5952297143, 5980201202, 6008167163, 6029981600, 6061270605, 6092655809, 6111504715, 6133547199, 6177840676, 6203227194, 6241476566, 6273457290, 6302292067, 6331303382, 6360348175, 6383023265, 6418747178, 6457847860, 6484003382, 6516810593, 6553009724, 6595942041, 6622445030, 6658989462, 6692352819, 6725838051, 6745997250, 6772912772, 6803291757, 6843934051, 6874484261, 6901743082, 6935884300, 6973594316, 7001088907, 7035566060, 7070161185, 7094469820, 7129248843, 7160651534, 7171131482, 7213146540, 7255359384, 7290686576, 7326128053, 7361623012, 7400846273, 7425874758, 7468889687, 7504869991, 7522922233, 7548196799, 7580778225, 7617105410, 7649920524, 7679189269, 7704842120, 7723146833, 7770982933, 7811628290, 7837536467, 7871008841, 7904513663, 7926905151, 7956844085, 7986858551, 8024457108, 8058398398, 8107621085, 8134183171, 8160843446, 8198963357, 8237218600, 8271742098, 8302491786, 8329485071, 8364283988, 8399150474, 8434142598, 8465348949, 8496576104, 8539623806, 8567130531, 8598608172, 8622291469, 8673722315, 8717425708, 8753254100, 8805170637, 8849291243, 8881450471, 8909681474, 8946012790, 8978403943, 9006815458, 9039368796, 9071984567, 9096515984, 9141560522, 9170326115, 9203237827, 9236250449, 9277627217, 9327407541, 9360748631, 9394112884, 9431808577, 9482160960, 9524234137, 9566436808, 9608774492, 9646964261, 9680969278, 9719342075, 9736418148, 9774970293, 9813599760, 9856652685, 9886875303, 9930118604, 9969160150, 10008312620, 10047553760, 10095595015, 10139429407, 10170177795, 10227478221, 10271685795, 10302657164, 10351563347, 10391734494, 10445394309, 10476802797, 10503714156, 10544198957, 10571271057, 10611971381, 10652721373, 10689018998, 10734567445, 10775633230, 10807631107, 10844367257, 10890323755, 10927126029, 10964033762, 11028889861, 11042770259, 11070663967, 11103217638, 11149856296, 11182573156, 11229449624, 11285895788, 11333054813, 11375683744, 11418332324, 11461126994, 11504059858, 11537503071, 11580590408, 11647756298, 11681449951, 11724888138, 11768453266, 11831513409, 11885071177, 11929029070, 11958356080, 11997530195, 12056428725, 12110611462, 12155082226, 12194683955, 12249299369, 12289136767, 12329036074, 12359004032, 12414100105, 12459272029, 12499568874, 12560153559, 12610695116, 12641101718, 12666510338, 12717438037, 12758280219, 12809347436, 12865730157, 12901657037, 12947983987, 12984096245, 13030614935, 13082507266, 13134457836, 13181418325, 13223160604, 13280727344, 13312210333, 13375336222, 13433329547, 13465067390, 13507408071, 13549881835, 13603071659, 13656349959, 13688337955, 13752630339, 13806229798, 13870888290, 13897864573, 13952009810, 13995377114, 14033412204, 14087877791, 14126081084, 14175233889, 14224598940, 14273932920, 14312474556, 14362107232, 14406196158, 14456025819, 14494859668, 14561455561, 14611686289, 14661945293, 14734836798, 14791032964, 14853059663, 14898238989, 14937821732, 14977501989, 15039973950, 15079888561, 15119800233, 15165469761, 15228507617, 15268750607, 15320438447, 15378057252, 15418462103, 15447401895, 15511124487, 15557589446, 15627418335, 15668229757, 15709193735, 15791329325, 15808939994, 15885444837, 15950321197, 15979861556, 16039093230, 16104493511, 16152107951, 16199791733, 16235650244, 16313409546, 16373500602, 16421658264, 16476007021, 16560687833, 16615250652, 16663833620, 16712566888, 16749230631, 16810298336, 16871478093, 16932820928, 16975887882, 17037620799, 17105606468, 17161422113, 17223570138, 17279561850, 17335616683, 17391885992, 17442007260, 17510969042, 17554975066, 17592810897, 17655941078, 17681230708, 17763606939, 17808060720, 17884439983, 17929051239, 17980144309, 18031413147, 18076327727, 18127667482, 18179071541, 18243555159, 18295259398, 18353543427, 18431415051, 18483420959, 18535601359, 18594312044, 18640075269, 18692584677, 18758284727, 18810884885, 18870272846, 18923198305, 18982752445, 19035816311, 19108883771, 19155469838, 19215523059, 19255677481, 19302615136, 19376488490, 19457262900, 19531453216, 19585529690, 19653260391, 19687206495, 19741535537, 19789176490, 19850503623, 19898299437, 19966768382, 20035314975, 20076511914, 20138502032, 20228335254, 20311430163, 20373836842, 20429408059, 20492102566, 20547891177, 20575869693, 20624745422, 20673769659, 20729862992, 20764993717, 20828357126, 20884796419, 20976800684, 21026405727, 21104435107, 21161391534, 21232672325, 21296912880, 21354196003, 21440220464, 21519285705, 21562516650, 21634682994, 21699815966, 21794020475, 21866679225, 21932207285, 21983288671, 22049063818, 22107677643, 22173671885, 22217803698, 22276631556, 22350297562, 22402006994, 22490805569, 22550196812, 22624542829, 22691588298, 22751243702, 22788569432, 22840923751, 22908442532, 22983574307, 23036226718, 23104081017, 23179649851, 23278052030, 23346395299, 23407288072, 23498676437, 23575069353, 23659247604, 23720529708, 23781933713, 23858943223, 23936032626, 23997830857, 24075282377, 24137374048, 24176236281, 24230676964, 24292949518, 24386651634, 24449289860, 24504099928, 24566917584, 24653378565, 24724310326, 24811177924, 24866619343, 24937943658, 25009380057, 25073025463, 25152665473, 25224526693, 25320534403, 25376656785, 25465008023, 25537425095, 25585758452, 25682745804, 25755573264, 25836749524, 25901780528, 25958741596, 26040216622, 26089191798, 26187328670, 26244730931, 26294009757, 26392735644, 26450382885, 26524641169, 26582518516, 26665326098, 26706773244, 26789840163, 26848113058, 26939761322, 26998188688, 27048384004, 27140525418, 27207610156, 27266447979, 27308528621, 27384392302, 27460401229, 27553468540, 27621270209, 27680649303, 27748680282, 27850912447, 27944772954, 28013167357, 28107417069, 28176126458, 28244923371, 28305197240, 28382836321, 28451992396, 28538576752, 28625323450, 28694800655
};

const int M = 300000, N = 100000;
LL d[M + 1];
int idx[2 * N];
vector<int> x[2 * N];

LL f(LL i) {
	if(d[i] != 2) { return 0; }
	
	inc(j, i) { if(d[j] != 2) { continue; }
		x[j + i].PB(i);
	}
	
	LL v = 0;
	inc(s, 2 * i) { if(d[s + i] != 2) { continue; }
		while(idx[s] < x[s].size() && x[s][idx[s]] < i) { idx[s]++; }
		v += idx[s];
	}
	
	return v;
}

int main() {
	inc1(i, M) { for(int j = i; j <= M; j += i) { d[j]++; } }
	
	/*
	LL sum = 0;
	inc1(i, N) {
		sum += f(i);
		if(i % 100 == 0) { cout << sum << ", "; }
	}
	cout << "end." << endl;
	*/
	
	int n;
	cin >> n;
	
	LL b = n / 100 * 100;
	inc1(i, b) { if(d[i] != 2) { continue; }
	inc(j, i)  { if(d[j] != 2) { continue; }
		x[j + i].PB(i);
	}
	}
	
	LL sum = memo[n / 100];
	incII(i, b + 1, n) {
		sum += f(i);
	}
	cout << sum << endl;
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード