Official

B - 3-smooth Numbers Editorial by en_translator

This problem can be solved with the following two approaches.

  1. Rephrase the condition to directly determine if the given number satisfies the condition
    1. A straightforward approach
    2. An approach that is easy to implement
  2. Enumerate all integers satisfying the conditions beforehand, and determine if the given number is contained in the predefined set

We describe both approaches.

1. Rephrasing the condition

For a natural number \(N\), if integers \(x\) and \(y\) satisfies \(N=2 ^ x3 ^ y\), then both \(x\) and \(y\) must be \(0\) or greater.

Proof

We show the contraposition: “if \(\bigl(x\lt0\) or \(y\lt0\bigr)\), then \(N\neq2 ^ x3 ^ y\).”

If we assume that \(x\lt0\) and \(y\lt0\), then \(0\lt2 ^ x3 ^ y\lt1\) holds; but no natural number \(N\) satisfies \(0\lt N\lt1\), so \(N\neq2 ^ x3 ^ y\) holds.

If we assume that \(x\lt0,y\geq0\), then \(2 ^ {-x}N\) is even and \(3 ^ y\) is odd, so \(2 ^ {-x}N\neq3 ^ y\). Multiplying both hand sides by \(2 ^ x\), we get \(N\neq2 ^ x3 ^ y\).

If we assume that \(x\geq0,y\lt0\), then \(3 ^ {-y}N\) is a multiple of three but \(2 ^ x\) is not, so \(3 ^ {-y}N\neq2 ^ x\). Multiplying both hand sides by \(3 ^ y\), we get \(N\neq2 ^ x3 ^ y\).

Therefore, we have shown that if \(\bigl(x\lt0\) or \(y\lt0\bigr)\), then \(N\neq2 ^ x3 ^ y\).

Let \(a\) be the maximum \(a\) such that \(2 ^ a\) divides \(N\), and \(b\) be the maximum \(b\) such that \(3 ^ b\) divides \(N\). Then, \(a\) and \(b\) are unique no matter \(N\) satisfies the condition in the problem statement or not.

\(N\) satisfies the condition if and only if these \(a\) and \(b\) satisfies \(N=2 ^ a3 ^ b\).

Proof

\(\lbrack\Rightarrow\rbrack\) We will show that, if there are integers \(x\) and \(y\) such that \(N=2 ^ x3^ y\), then \(a=x\) and \(b=y\), Since it is obvious that \(N\) is divisible by \(2 ^ x\), we will show that is indivisible by \(2 ^ (x+1)\). \(N=2 ^ x3 ^ y\) is the prime factorization of \(N\). Since the prime factorization of an integer is unique, there is no integer \(k\) satisfying \(N=2 ^ {x+1}k\), so \(a=x\) has been shown. Same applies to \(b=y\).

\(\lbrack\Leftarrow\rbrack\) Obviously, if \(x=a\) and \(y=b\), the condition is satisfied.

Thus, it is sufficient to find these \(a\) and \(b\).

1-1. Straightforward approach

One can successively increment \(a\) and \(b\) and stop the iteration once it is indivisible, in order to find \(a\) and \(b\).

The following is sample code.

N = int(input())

ord_2 = 0
while N % pow(2, ord_2 + 1) == 0: # If N is divisible even by incrementing x,
    ord_2 += 1 # actually increment it

ord_3 = 0
while N % pow(3, ord_3 + 1) == 0: # If N is divisible even by incrementing y,
    ord_3 += 1 # actually increment it

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

1-2. An approach that is easy to implement

Further consideration yields the following condition.

\(N\) satisfies the condition in the problem statement if and only if \(N\) ends up being \(1\) by:

  1. repeatedly dividing \(N\) by \(2\) until it \(N\) is divisible by \(2\), and
  2. repeatedly dividing \(N\) by \(3\) until it \(N\) is divisible by \(3\).

All that left is to implement it.

The following is sample code.

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. Precomputing all integers that satisfy the condition

There are at most \(\log _ 2(10 ^ {18})\times\log _ 3(10 ^ {18})=2255.8305\ldots\) pairs of integers \((x, y)\) such that \(2 ^ x3 ^ y\leq10 ^ {18}\). (This evaluation is obtained by taking the logarithm of both hand sides of the necessary inequalities \(2 ^ x\leq10 ^ {18}\) and \(3 ^ y\leq10 ^ {18}\). Therefore, there are at most \(2255\) integers \(N\) that may satisfy the condition. (Actually, there are even fewer; only \(1178\) of them actually satisfies the condition.)

Therefore, it is sufficient to precompute these \(1178\) integers \(N\) and determine if the given \(N\) is contained in this set.

The following is sample code.

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: