Official

C - 3-smooth Numbers Editorial by MMNMM

この問題は、次の \(2\) つの方針で解くことができます。

  1. 条件を言い換えて、与えられた数が言い換えた条件を満たすか直接判定する方針
    1. 素直な方針
    2. より実装が簡単な方針
  2. 条件を満たす数を事前にすべて計算しておき、与えられた数がその中に含まれるか判定する方針

それぞれの方針について解説します。

1. 条件を言い換える方針

自然数 \(N\) について整数 \(x,y\) が \(N=2 ^ x3 ^ y\) を満たすなら、\(x,y\) はどちらも \(0\) 以上である必要があります。

証明

対偶を示します。 示したい命題の対偶は「\(\bigl(x\lt0\) もしくは \(y\lt0\bigr)\) ならば \(N\neq2 ^ x3 ^ y\)」です。

\(x\lt0\) かつ \(y\lt0\) と仮定すると、\(0\lt2 ^ x3 ^ y\lt1\) が成り立ちますが、自然数 \(N\) が \(0\lt N\lt1\) を満たすことはないため、\(N\neq2 ^ x3 ^ y\) が成り立ちます。

\(x\lt0,y\geq0\) と仮定すると、\(2 ^ {-x}N\) は偶数で \(3 ^ y\) は奇数なので、\(2 ^ {-x}N\neq3 ^ y\) が成り立ちます。これの両辺を \(2 ^ x\) 倍して、\(N\neq2 ^ x3 ^ y\) が成り立ちます。

\(x\geq0,y\lt0\) と仮定すると、\(3 ^ {-y}N\) は \(3\) の倍数で \(2 ^ x\) は \(3\) の倍数でないため、\(3 ^ {-y}N\neq2 ^ x\) が成り立ちます。これの両辺を \(3 ^ y\) 倍して、\(N\neq2 ^ x3 ^ y\) が成り立ちます。

よって、\(\bigl(x\lt0\) もしくは \(y\lt0\bigr)\) ならば \(N\neq2 ^ x3 ^ y\) が示されました。

\(a\) を「 \(2 ^ a\) が \(N\) を割り切る最大の \(a\) 」とし、\(b\) を「 \(3 ^ b\) が \(N\) を割り切る最大の \(b\) 」とします。 このとき、\(N\) が問題文の条件を満たすか満たさないかによらずただ一つ \(a,b\) が定まります。

\(N\) が条件を満たすことは、この \(a,b\) が \(N=2 ^ a3 ^ b\) を満たすことと同値です。

証明

\(\lbrack\Rightarrow\rbrack\) \(N=2 ^ x3^ y\) を満たす整数 \(x,y\) が存在するとき、\(a=x,b=y\) となることを示します。\(N\) が \(2 ^ x\) で割り切れることは明らかなので、\(2 ^ {x+1}\) で割り切れないことを示します。\(N=2 ^ x3 ^ y\) は \(N\) の素因数分解になっています。素因数分解の一意性より、\(N=2 ^ {x+1}k\) を満たす整数 \(k\) は存在せず、\(a=x\) が示されました。\(b=y\) も同様に示されます。

\(\lbrack\Leftarrow\rbrack\) 明らかに、\(x=a,y=b\) とすると条件を満たします。

よって、この \(a,b\) を求められればよいです。

1-1. 素直な方針

小さい方から \(a,b\) の候補を試し、割り切れなくなったところで探索を打ち切ることで \(a,b\) が求められます。

実装例は以下のようになります。

N = int(input())

ord_2 = 0
while N % pow(2, ord_2 + 1) == 0: # 1 増やしても割り切れるなら
    ord_2 += 1 # 1 増やす

ord_3 = 0
while N % pow(3, ord_3 + 1) == 0: # 1 増やしても割り切れるなら
    ord_3 += 1 # 1 増やす

if N == pow(2, ord_2) * pow(3, ord_3):
    print('Yes')
else:
    print('No')

1-2. より実装が簡単な方針

この条件は、さらに考察することで次の条件になります。

\(N\) が問題文の条件を満たすことは、次の操作をおこなった結果が \(1\) になることと同値である。

  1. \(N\) が \(2\) で割り切れる限り、\(N\) を \(2\) で割る。
  2. \(N\) が \(3\) で割り切れる限り、\(N\) を \(3\) で割る。

あとは、これを実装すればよいです。

実装例は以下のようになります。

N = int(input())

while N % 2 == 0:
    N //= 2

while N % 3 == 0:
    N //= 3

if N == 1:
    print('Yes')
else:
    print('No')

#include <iostream>

using namespace std;

int main() {
    long N;
    cin >> N;
    
    while (N % 3 == 0)
        N /= 3;
    while (N % 2 == 0)
        N /= 2;
    
    if (N == 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}

2. 条件を満たす数を事前にすべて計算する方針

\(2 ^ x3 ^ y\leq10 ^ {18}\) を満たすような整数 \(x,y\) は、たかだか \(\log _ 2(10 ^ {18})\times\log _ 3(10 ^ {18})=2255.8305\ldots\) 個しか存在しません（この評価は、\(2 ^ x\leq10 ^ {18},3 ^ y\leq10 ^ {18}\) が必要なことから両辺の対数を取って得られます）。 よって、条件を満たすような \(N\) としてありえる整数もたかだか \(2255\) 個しかありません（実際はもっと少なく、\(1178\) 個だけです）。

なので、この \(1178\) 個の \(N\) を事前に計算しておき、与えられた \(N\) がこの中に存在しているか判定すればよいです。

実装例は以下のようになります。

all_N = [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2187, 2304, 2592, 2916, 3072, 3456, 3888, 4096, 4374, 4608, 5184, 5832, 6144, 6561, 6912, 7776, 8192, 8748, 9216, 10368, 11664, 12288, 13122, 13824, 15552, 16384, 17496, 18432, 19683, 20736, 23328, 24576, 26244, 27648, 31104, 32768, 34992, 36864, 39366, 41472, 46656, 49152, 52488, 55296, 59049, 62208, 65536, 69984, 73728, 78732, 82944, 93312, 98304, 104976, 110592, 118098, 124416, 131072, 139968, 147456, 157464, 165888, 177147, 186624, 196608, 209952, 221184, 236196, 248832, 262144, 279936, 294912, 314928, 331776, 354294, 373248, 393216, 419904, 442368, 472392, 497664, 524288, 531441, 559872, 589824, 629856, 663552, 708588, 746496, 786432, 839808, 884736, 944784, 995328, 1048576, 1062882, 1119744, 1179648, 1259712, 1327104, 1417176, 1492992, 1572864, 1594323, 1679616, 1769472, 1889568, 1990656, 2097152, 2125764, 2239488, 2359296, 2519424, 2654208, 2834352, 2985984, 3145728, 3188646, 3359232, 3538944, 3779136, 3981312, 4194304, 4251528, 4478976, 4718592, 4782969, 5038848, 5308416, 5668704, 5971968, 6291456, 6377292, 6718464, 7077888, 7558272, 7962624, 8388608, 8503056, 8957952, 9437184, 9565938, 10077696, 10616832, 11337408, 11943936, 12582912, 12754584, 13436928, 14155776, 14348907, 15116544, 15925248, 16777216, 17006112, 17915904, 18874368, 19131876, 20155392, 21233664, 22674816, 23887872, 25165824, 25509168, 26873856, 28311552, 28697814, 30233088, 31850496, 33554432, 34012224, 35831808, 37748736, 38263752, 40310784, 42467328, 43046721, 45349632, 47775744, 50331648, 51018336, 53747712, 56623104, 57395628, 60466176, 63700992, 67108864, 68024448, 71663616, 75497472, 76527504, 80621568, 84934656, 86093442, 90699264, 95551488, 100663296, 102036672, 107495424, 113246208, 114791256, 120932352, 127401984, 129140163, 134217728, 136048896, 143327232, 150994944, 153055008, 161243136, 169869312, 172186884, 181398528, 191102976, 201326592, 204073344, 214990848, 226492416, 229582512, 241864704, 254803968, 258280326, 268435456, 272097792, 286654464, 301989888, 306110016, 322486272, 339738624, 344373768, 362797056, 382205952, 387420489, 402653184, 408146688, 429981696, 452984832, 459165024, 483729408, 509607936, 516560652, 536870912, 544195584, 573308928, 603979776, 612220032, 644972544, 679477248, 688747536, 725594112, 764411904, 774840978, 805306368, 816293376, 859963392, 905969664, 918330048, 967458816, 1019215872, 1033121304, 1073741824, 1088391168, 1146617856, 1162261467, 1207959552, 1224440064, 1289945088, 1358954496, 1377495072, 1451188224, 1528823808, 1549681956, 1610612736, 1632586752, 1719926784, 1811939328, 1836660096, 1934917632, 2038431744, 2066242608, 2147483648, 2176782336, 2293235712, 2324522934, 2415919104, 2448880128, 2579890176, 2717908992, 2754990144, 2902376448, 3057647616, 3099363912, 3221225472, 3265173504, 3439853568, 3486784401, 3623878656, 3673320192, 3869835264, 4076863488, 4132485216, 4294967296, 4353564672, 4586471424, 4649045868, 4831838208, 4897760256, 5159780352, 5435817984, 5509980288, 5804752896, 6115295232, 6198727824, 6442450944, 6530347008, 6879707136, 6973568802, 7247757312, 7346640384, 7739670528, 8153726976, 8264970432, 8589934592, 8707129344, 9172942848, 9298091736, 9663676416, 9795520512, 10319560704, 10460353203, 10871635968, 11019960576, 11609505792, 12230590464, 12397455648, 12884901888, 13060694016, 13759414272, 13947137604, 14495514624, 14693280768, 15479341056, 16307453952, 16529940864, 17179869184, 17414258688, 18345885696, 18596183472, 19327352832, 19591041024, 20639121408, 20920706406, 21743271936, 22039921152, 23219011584, 24461180928, 24794911296, 25769803776, 26121388032, 27518828544, 27894275208, 28991029248, 29386561536, 30958682112, 31381059609, 32614907904, 33059881728, 34359738368, 34828517376, 36691771392, 37192366944, 38654705664, 39182082048, 41278242816, 41841412812, 43486543872, 44079842304, 46438023168, 48922361856, 49589822592, 51539607552, 52242776064, 55037657088, 55788550416, 57982058496, 58773123072, 61917364224, 62762119218, 65229815808, 66119763456, 68719476736, 69657034752, 73383542784, 74384733888, 77309411328, 78364164096, 82556485632, 83682825624, 86973087744, 88159684608, 92876046336, 94143178827, 97844723712, 99179645184, 103079215104, 104485552128, 110075314176, 111577100832, 115964116992, 117546246144, 123834728448, 125524238436, 130459631616, 132239526912, 137438953472, 139314069504, 146767085568, 148769467776, 154618822656, 156728328192, 165112971264, 167365651248, 173946175488, 176319369216, 185752092672, 188286357654, 195689447424, 198359290368, 206158430208, 208971104256, 220150628352, 223154201664, 231928233984, 235092492288, 247669456896, 251048476872, 260919263232, 264479053824, 274877906944, 278628139008, 282429536481, 293534171136, 297538935552, 309237645312, 313456656384, 330225942528, 334731302496, 347892350976, 352638738432, 371504185344, 376572715308, 391378894848, 396718580736, 412316860416, 417942208512, 440301256704, 446308403328, 463856467968, 470184984576, 495338913792, 502096953744, 521838526464, 528958107648, 549755813888, 557256278016, 564859072962, 587068342272, 595077871104, 618475290624, 626913312768, 660451885056, 669462604992, 695784701952, 705277476864, 743008370688, 753145430616, 782757789696, 793437161472, 824633720832, 835884417024, 847288609443, 880602513408, 892616806656, 927712935936, 940369969152, 990677827584, 1004193907488, 1043677052928, 1057916215296, 1099511627776, 1114512556032, 1129718145924, 1174136684544, 1190155742208, 1236950581248, 1253826625536, 1320903770112, 1338925209984, 1391569403904, 1410554953728, 1486016741376, 1506290861232, 1565515579392, 1586874322944, 1649267441664, 1671768834048, 1694577218886, 1761205026816, 1785233613312, 1855425871872, 1880739938304, 1981355655168, 2008387814976, 2087354105856, 2115832430592, 2199023255552, 2229025112064, 2259436291848, 2348273369088, 2380311484416, 2473901162496, 2507653251072, 2541865828329, 2641807540224, 2677850419968, 2783138807808, 2821109907456, 2972033482752, 3012581722464, 3131031158784, 3173748645888, 3298534883328, 3343537668096, 3389154437772, 3522410053632, 3570467226624, 3710851743744, 3761479876608, 3962711310336, 4016775629952, 4174708211712, 4231664861184, 4398046511104, 4458050224128, 4518872583696, 4696546738176, 4760622968832, 4947802324992, 5015306502144, 5083731656658, 5283615080448, 5355700839936, 5566277615616, 5642219814912, 5944066965504, 6025163444928, 6262062317568, 6347497291776, 6597069766656, 6687075336192, 6778308875544, 7044820107264, 7140934453248, 7421703487488, 7522959753216, 7625597484987, 7925422620672, 8033551259904, 8349416423424, 8463329722368, 8796093022208, 8916100448256, 9037745167392, 9393093476352, 9521245937664, 9895604649984, 10030613004288, 10167463313316, 10567230160896, 10711401679872, 11132555231232, 11284439629824, 11888133931008, 12050326889856, 12524124635136, 12694994583552, 13194139533312, 13374150672384, 13556617751088, 14089640214528, 14281868906496, 14843406974976, 15045919506432, 15251194969974, 15850845241344, 16067102519808, 16698832846848, 16926659444736, 17592186044416, 17832200896512, 18075490334784, 18786186952704, 19042491875328, 19791209299968, 20061226008576, 20334926626632, 21134460321792, 21422803359744, 22265110462464, 22568879259648, 22876792454961, 23776267862016, 24100653779712, 25048249270272, 25389989167104, 26388279066624, 26748301344768, 27113235502176, 28179280429056, 28563737812992, 29686813949952, 30091839012864, 30502389939948, 31701690482688, 32134205039616, 33397665693696, 33853318889472, 35184372088832, 35664401793024, 36150980669568, 37572373905408, 38084983750656, 39582418599936, 40122452017152, 40669853253264, 42268920643584, 42845606719488, 44530220924928, 45137758519296, 45753584909922, 47552535724032, 48201307559424, 50096498540544, 50779978334208, 52776558133248, 53496602689536, 54226471004352, 56358560858112, 57127475625984, 59373627899904, 60183678025728, 61004779879896, 63403380965376, 64268410079232, 66795331387392, 67706637778944, 68630377364883, 70368744177664, 71328803586048, 72301961339136, 75144747810816, 76169967501312, 79164837199872, 80244904034304, 81339706506528, 84537841287168, 85691213438976, 89060441849856, 90275517038592, 91507169819844, 95105071448064, 96402615118848, 100192997081088, 101559956668416, 105553116266496, 106993205379072, 108452942008704, 112717121716224, 114254951251968, 118747255799808, 120367356051456, 122009559759792, 126806761930752, 128536820158464, 133590662774784, 135413275557888, 137260754729766, 140737488355328, 142657607172096, 144603922678272, 150289495621632, 152339935002624, 158329674399744, 160489808068608, 162679413013056, 169075682574336, 171382426877952, 178120883699712, 180551034077184, 183014339639688, 190210142896128, 192805230237696, 200385994162176, 203119913336832, 205891132094649, 211106232532992, 213986410758144, 216905884017408, 225434243432448, 228509902503936, 237494511599616, 240734712102912, 244019119519584, 253613523861504, 257073640316928, 267181325549568, 270826551115776, 274521509459532, 281474976710656, 285315214344192, 289207845356544, 300578991243264, 304679870005248, 316659348799488, 320979616137216, 325358826026112, 338151365148672, 342764853755904, 356241767399424, 361102068154368, 366028679279376, 380420285792256, 385610460475392, 400771988324352, 406239826673664, 411782264189298, 422212465065984, 427972821516288, 433811768034816, 450868486864896, 457019805007872, 474989023199232, 481469424205824, 488038239039168, 507227047723008, 514147280633856, 534362651099136, 541653102231552, 549043018919064, 562949953421312, 570630428688384, 578415690713088, 601157982486528, 609359740010496, 617673396283947, 633318697598976, 641959232274432, 650717652052224, 676302730297344, 685529707511808, 712483534798848, 722204136308736, 732057358558752, 760840571584512, 771220920950784, 801543976648704, 812479653347328, 823564528378596, 844424930131968, 855945643032576, 867623536069632, 901736973729792, 914039610015744, 949978046398464, 962938848411648, 976076478078336, 1014454095446016, 1028294561267712, 1068725302198272, 1083306204463104, 1098086037838128, 1125899906842624, 1141260857376768, 1156831381426176, 1202315964973056, 1218719480020992, 1235346792567894, 1266637395197952, 1283918464548864, 1301435304104448, 1352605460594688, 1371059415023616, 1424967069597696, 1444408272617472, 1464114717117504, 1521681143169024, 1542441841901568, 1603087953297408, 1624959306694656, 1647129056757192, 1688849860263936, 1711891286065152, 1735247072139264, 1803473947459584, 1828079220031488, 1853020188851841, 1899956092796928, 1925877696823296, 1952152956156672, 2028908190892032, 2056589122535424, 2137450604396544, 2166612408926208, 2196172075676256, 2251799813685248, 2282521714753536, 2313662762852352, 2404631929946112, 2437438960041984, 2470693585135788, 2533274790395904, 2567836929097728, 2602870608208896, 2705210921189376, 2742118830047232, 2849934139195392, 2888816545234944, 2928229434235008, 3043362286338048, 3084883683803136, 3206175906594816, 3249918613389312, 3294258113514384, 3377699720527872, 3423782572130304, 3470494144278528, 3606947894919168, 3656158440062976, 3706040377703682, 3799912185593856, 3851755393646592, 3904305912313344, 4057816381784064, 4113178245070848, 4274901208793088, 4333224817852416, 4392344151352512, 4503599627370496, 4565043429507072, 4627325525704704, 4809263859892224, 4874877920083968, 4941387170271576, 5066549580791808, 5135673858195456, 5205741216417792, 5410421842378752, 5484237660094464, 5559060566555523, 5699868278390784, 5777633090469888, 5856458868470016, 6086724572676096, 6169767367606272, 6412351813189632, 6499837226778624, 6588516227028768, 6755399441055744, 6847565144260608, 6940988288557056, 7213895789838336, 7312316880125952, 7412080755407364, 7599824371187712, 7703510787293184, 7808611824626688, 8115632763568128, 8226356490141696, 8549802417586176, 8666449635704832, 8784688302705024, 9007199254740992, 9130086859014144, 9254651051409408, 9618527719784448, 9749755840167936, 9882774340543152, 10133099161583616, 10271347716390912, 10411482432835584, 10820843684757504, 10968475320188928, 11118121133111046, 11399736556781568, 11555266180939776, 11712917736940032, 12173449145352192, 12339534735212544, 12824703626379264, 12999674453557248, 13177032454057536, 13510798882111488, 13695130288521216, 13881976577114112, 14427791579676672, 14624633760251904, 14824161510814728, 15199648742375424, 15407021574586368, 15617223649253376, 16231265527136256, 16452712980283392, 16677181699666569, 17099604835172352, 17332899271409664, 17569376605410048, 18014398509481984, 18260173718028288, 18509302102818816, 19237055439568896, 19499511680335872, 19765548681086304, 20266198323167232, 20542695432781824, 20822964865671168, 21641687369515008, 21936950640377856, 22236242266222092, 22799473113563136, 23110532361879552, 23425835473880064, 24346898290704384, 24679069470425088, 25649407252758528, 25999348907114496, 26354064908115072, 27021597764222976, 27390260577042432, 27763953154228224, 28855583159353344, 29249267520503808, 29648323021629456, 30399297484750848, 30814043149172736, 31234447298506752, 32462531054272512, 32905425960566784, 33354363399333138, 34199209670344704, 34665798542819328, 35138753210820096, 36028797018963968, 36520347436056576, 37018604205637632, 38474110879137792, 38999023360671744, 39531097362172608, 40532396646334464, 41085390865563648, 41645929731342336, 43283374739030016, 43873901280755712, 44472484532444184, 45598946227126272, 46221064723759104, 46851670947760128, 48693796581408768, 49358138940850176, 50031545098999707, 51298814505517056, 51998697814228992, 52708129816230144, 54043195528445952, 54780521154084864, 55527906308456448, 57711166318706688, 58498535041007616, 59296646043258912, 60798594969501696, 61628086298345472, 62468894597013504, 64925062108545024, 65810851921133568, 66708726798666276, 68398419340689408, 69331597085638656, 70277506421640192, 72057594037927936, 73040694872113152, 74037208411275264, 76948221758275584, 77998046721343488, 79062194724345216, 81064793292668928, 82170781731127296, 83291859462684672, 86566749478060032, 87747802561511424, 88944969064888368, 91197892454252544, 92442129447518208, 93703341895520256, 97387593162817536, 98716277881700352, 100063090197999414, 102597629011034112, 103997395628457984, 105416259632460288, 108086391056891904, 109561042308169728, 111055812616912896, 115422332637413376, 116997070082015232, 118593292086517824, 121597189939003392, 123256172596690944, 124937789194027008, 129850124217090048, 131621703842267136, 133417453597332552, 136796838681378816, 138663194171277312, 140555012843280384, 144115188075855872, 146081389744226304, 148074416822550528, 150094635296999121, 153896443516551168, 155996093442686976, 158124389448690432, 162129586585337856, 164341563462254592, 166583718925369344, 173133498956120064, 175495605123022848, 177889938129776736, 182395784908505088, 184884258895036416, 187406683791040512, 194775186325635072, 197432555763400704, 200126180395998828, 205195258022068224, 207994791256915968, 210832519264920576, 216172782113783808, 219122084616339456, 222111625233825792, 230844665274826752, 233994140164030464, 237186584173035648, 243194379878006784, 246512345193381888, 249875578388054016, 259700248434180096, 263243407684534272, 266834907194665104, 273593677362757632, 277326388342554624, 281110025686560768, 288230376151711744, 292162779488452608, 296148833645101056, 300189270593998242, 307792887033102336, 311992186885373952, 316248778897380864, 324259173170675712, 328683126924509184, 333167437850738688, 346266997912240128, 350991210246045696, 355779876259553472, 364791569817010176, 369768517790072832, 374813367582081024, 389550372651270144, 394865111526801408, 400252360791997656, 410390516044136448, 415989582513831936, 421665038529841152, 432345564227567616, 438244169232678912, 444223250467651584, 450283905890997363, 461689330549653504, 467988280328060928, 474373168346071296, 486388759756013568, 493024690386763776, 499751156776108032, 519400496868360192, 526486815369068544, 533669814389330208, 547187354725515264, 554652776685109248, 562220051373121536, 576460752303423488, 584325558976905216, 592297667290202112, 600378541187996484, 615585774066204672, 623984373770747904, 632497557794761728, 648518346341351424, 657366253849018368, 666334875701477376, 692533995824480256, 701982420492091392, 711559752519106944, 729583139634020352, 739537035580145664, 749626735164162048, 779100745302540288, 789730223053602816, 800504721583995312, 820781032088272896, 831979165027663872, 843330077059682304, 864691128455135232, 876488338465357824, 888446500935303168, 900567811781994726, 923378661099307008, 935976560656121856, 948746336692142592, 972777519512027136, 986049380773527552, 999502313552216064]

N = int(input())

if N in all_N:
    print('Yes')
else:
    print('No')

posted:
last update: