找出一个数字是否有P ^ Qforms?

我最近出现了在线编码测试。 我被打了一个问题,即

给出数字N,发现上述数字是否是P ^ Q(P power Q)forms。 我使用Brute force方法(满足个别号码)来解决这个问题,但结果是超时。 所以我需要高效的算法。

输入:9

out put:是的

输入:125

out put:是的

输入:27

out put:是的

约束:2 <N <100000

如果我们假设非平凡的情况,那么约束将是这样的:

  • N = <2,100000)
  • P>1
  • Q>1

这可以通过标记所有功率大于1N的结果来解决。 现在问题是你需要优化单个查询还是其中许多查询? 如果您只需要单个查询,那么您不需要内存中的筛选表,只需迭代直到达到N然后停止(因此在最坏的情况下,当N不是formsP^Q这将计算整个筛子)。 否则初始化这样的表,然后只使用它。 由于N很小,我选择全桌。

 const int n=100000; int sieve[n]={255}; // for simplicity 1 int/number but it is waste of space can use 1 bit per number instead int powers(int x) { // init sieve table if not already inited if (sieve[0]==255) { int i,p; for (i=0;i1;p--) // process all non trivial P for (i=p*p;i 
  • 在矿井设置中,第一次呼叫花费了0.548 ms ,其他则是不可测量的小时间
  • 它返回P所以如果P!=0那么数字就是P^Qforms,所以你可以直接使用它作为bool ,你也可以通过划分轻松获得Q ,或者你可以创建另一个带Q筛子,如果它更快你还需要P,Q

这里发现所有非平凡的权力N<100000

  4 = 2^q 8 = 2^q 9 = 3^q 16 = 2^q 25 = 5^q 27 = 3^q 32 = 2^q 36 = 6^q 49 = 7^q 64 = 2^q 81 = 3^q 100 = 10^q 121 = 11^q 125 = 5^q 128 = 2^q 144 = 12^q 169 = 13^q 196 = 14^q 216 = 6^q 225 = 15^q 243 = 3^q 256 = 2^q 289 = 17^q 324 = 18^q 343 = 7^q 361 = 19^q 400 = 20^q 441 = 21^q 484 = 22^q 512 = 2^q 529 = 23^q 576 = 24^q 625 = 5^q 676 = 26^q 729 = 3^q 784 = 28^q 841 = 29^q 900 = 30^q 961 = 31^q 1000 = 10^q 1024 = 2^q 1089 = 33^q 1156 = 34^q 1225 = 35^q 1296 = 6^q 1331 = 11^q 1369 = 37^q 1444 = 38^q 1521 = 39^q 1600 = 40^q 1681 = 41^q 1728 = 12^q 1764 = 42^q 1849 = 43^q 1936 = 44^q 2025 = 45^q 2048 = 2^q 2116 = 46^q 2187 = 3^q 2197 = 13^q 2209 = 47^q 2304 = 48^q 2401 = 7^q 2500 = 50^q 2601 = 51^q 2704 = 52^q 2744 = 14^q 2809 = 53^q 2916 = 54^q 3025 = 55^q 3125 = 5^q 3136 = 56^q 3249 = 57^q 3364 = 58^q 3375 = 15^q 3481 = 59^q 3600 = 60^q 3721 = 61^q 3844 = 62^q 3969 = 63^q 4096 = 2^q 4225 = 65^q 4356 = 66^q 4489 = 67^q 4624 = 68^q 4761 = 69^q 4900 = 70^q 4913 = 17^q 5041 = 71^q 5184 = 72^q 5329 = 73^q 5476 = 74^q 5625 = 75^q 5776 = 76^q 5832 = 18^q 5929 = 77^q 6084 = 78^q 6241 = 79^q 6400 = 80^q 6561 = 3^q 6724 = 82^q 6859 = 19^q 6889 = 83^q 7056 = 84^q 7225 = 85^q 7396 = 86^q 7569 = 87^q 7744 = 88^q 7776 = 6^q 7921 = 89^q 8000 = 20^q 8100 = 90^q 8192 = 2^q 8281 = 91^q 8464 = 92^q 8649 = 93^q 8836 = 94^q 9025 = 95^q 9216 = 96^q 9261 = 21^q 9409 = 97^q 9604 = 98^q 9801 = 99^q 10000 = 10^q 10201 = 101^q 10404 = 102^q 10609 = 103^q 10648 = 22^q 10816 = 104^q 11025 = 105^q 11236 = 106^q 11449 = 107^q 11664 = 108^q 11881 = 109^q 12100 = 110^q 12167 = 23^q 12321 = 111^q 12544 = 112^q 12769 = 113^q 12996 = 114^q 13225 = 115^q 13456 = 116^q 13689 = 117^q 13824 = 24^q 13924 = 118^q 14161 = 119^q 14400 = 120^q 14641 = 11^q 14884 = 122^q 15129 = 123^q 15376 = 124^q 15625 = 5^q 15876 = 126^q 16129 = 127^q 16384 = 2^q 16641 = 129^q 16807 = 7^q 16900 = 130^q 17161 = 131^q 17424 = 132^q 17576 = 26^q 17689 = 133^q 17956 = 134^q 18225 = 135^q 18496 = 136^q 18769 = 137^q 19044 = 138^q 19321 = 139^q 19600 = 140^q 19683 = 3^q 19881 = 141^q 20164 = 142^q 20449 = 143^q 20736 = 12^q 21025 = 145^q 21316 = 146^q 21609 = 147^q 21904 = 148^q 21952 = 28^q 22201 = 149^q 22500 = 150^q 22801 = 151^q 23104 = 152^q 23409 = 153^q 23716 = 154^q 24025 = 155^q 24336 = 156^q 24389 = 29^q 24649 = 157^q 24964 = 158^q 25281 = 159^q 25600 = 160^q 25921 = 161^q 26244 = 162^q 26569 = 163^q 26896 = 164^q 27000 = 30^q 27225 = 165^q 27556 = 166^q 27889 = 167^q 28224 = 168^q 28561 = 13^q 28900 = 170^q 29241 = 171^q 29584 = 172^q 29791 = 31^q 29929 = 173^q 30276 = 174^q 30625 = 175^q 30976 = 176^q 31329 = 177^q 31684 = 178^q 32041 = 179^q 32400 = 180^q 32761 = 181^q 32768 = 2^q 33124 = 182^q 33489 = 183^q 33856 = 184^q 34225 = 185^q 34596 = 186^q 34969 = 187^q 35344 = 188^q 35721 = 189^q 35937 = 33^q 36100 = 190^q 36481 = 191^q 36864 = 192^q 37249 = 193^q 37636 = 194^q 38025 = 195^q 38416 = 14^q 38809 = 197^q 39204 = 198^q 39304 = 34^q 39601 = 199^q 40000 = 200^q 40401 = 201^q 40804 = 202^q 41209 = 203^q 41616 = 204^q 42025 = 205^q 42436 = 206^q 42849 = 207^q 42875 = 35^q 43264 = 208^q 43681 = 209^q 44100 = 210^q 44521 = 211^q 44944 = 212^q 45369 = 213^q 45796 = 214^q 46225 = 215^q 46656 = 6^q 47089 = 217^q 47524 = 218^q 47961 = 219^q 48400 = 220^q 48841 = 221^q 49284 = 222^q 49729 = 223^q 50176 = 224^q 50625 = 15^q 50653 = 37^q 51076 = 226^q 51529 = 227^q 51984 = 228^q 52441 = 229^q 52900 = 230^q 53361 = 231^q 53824 = 232^q 54289 = 233^q 54756 = 234^q 54872 = 38^q 55225 = 235^q 55696 = 236^q 56169 = 237^q 56644 = 238^q 57121 = 239^q 57600 = 240^q 58081 = 241^q 58564 = 242^q 59049 = 3^q 59319 = 39^q 59536 = 244^q 60025 = 245^q 60516 = 246^q 61009 = 247^q 61504 = 248^q 62001 = 249^q 62500 = 250^q 63001 = 251^q 63504 = 252^q 64000 = 40^q 64009 = 253^q 64516 = 254^q 65025 = 255^q 65536 = 2^q 66049 = 257^q 66564 = 258^q 67081 = 259^q 67600 = 260^q 68121 = 261^q 68644 = 262^q 68921 = 41^q 69169 = 263^q 69696 = 264^q 70225 = 265^q 70756 = 266^q 71289 = 267^q 71824 = 268^q 72361 = 269^q 72900 = 270^q 73441 = 271^q 73984 = 272^q 74088 = 42^q 74529 = 273^q 75076 = 274^q 75625 = 275^q 76176 = 276^q 76729 = 277^q 77284 = 278^q 77841 = 279^q 78125 = 5^q 78400 = 280^q 78961 = 281^q 79507 = 43^q 79524 = 282^q 80089 = 283^q 80656 = 284^q 81225 = 285^q 81796 = 286^q 82369 = 287^q 82944 = 288^q 83521 = 17^q 84100 = 290^q 84681 = 291^q 85184 = 44^q 85264 = 292^q 85849 = 293^q 86436 = 294^q 87025 = 295^q 87616 = 296^q 88209 = 297^q 88804 = 298^q 89401 = 299^q 90000 = 300^q 90601 = 301^q 91125 = 45^q 91204 = 302^q 91809 = 303^q 92416 = 304^q 93025 = 305^q 93636 = 306^q 94249 = 307^q 94864 = 308^q 95481 = 309^q 96100 = 310^q 96721 = 311^q 97336 = 46^q 97344 = 312^q 97969 = 313^q 98596 = 314^q 99225 = 315^q 99856 = 316^q 
  • 它需要62.6 ms包括第一个初始化调用(和字符串输出到备忘录,它比计算本身慢得多)没有字符串只花了1.25 ms