找到一个数是否为P ^ Q表格或没有? [英] Finding whether a number has P^Q form or not?
问题描述
我最近在网上出现的测试编码。我感到震惊一个问题即
I have recently appeared online coding Test. I was struck one question i.e
N被赋予找到上述编号的数字为P ^ Q(P功率Q)的形式或没有。我没有用强制的方法(满足个人数字),但结果在时间上出了问题。所以我需要高效的算法。
A number N is given finding the above number is P^Q(P power Q) form or not. I did the question using Brute force method (satisfying for individual number) but that result in time out. SO I need Efficient algorithm.
输入:9
出地说:是的。
输入:125
出地说:是的。
输入:27
出地说:是的。
约束:2'; N< 100000
Constraints: 2<N<100000
推荐答案
如果我们假设不平凡的情况下再限制将是这样的:
if we assume non trivial cases then the constraints would be something like this:
-
N =&LT; 2,100000)
-
P&GT; 1
-
Q&GT; 1
N = <2,100000)
P>1
Q>1
这可以通过筛标志着一切权力更大然后 1
高达 N $ C $亟待解决C>的结果。现在的问题是,你需要优化单个查询或很多人?如果你只需要单一的查询,那么你就不需要在内存中筛表,你只是迭代,直到撞到
不是在形式上 N
然后停止(因此,在最坏的情况下,当<$ C $ ç> N 点^ Q
这将计算整个筛)。否则,这样的初始化表一次,然后只用它。由于 N
小我去的全表。
This can be solved by sieves that mark all powers bigger then 1
up to N
of the result. Now the question is do you need to optimize single query or many of them ? If you need just single query then you do not need the sieve table in memory, you just iterate until hit the N
and then stop (so in worst case when N
is not in form P^Q
this would compute the whole sieve). Otherwise init such table once and then just use it. As N
is small I go for the full table.
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;i<n;i++) sieve[i]=0; // clear sieve
for (p=sqrt(n);p>1;p--) // process all non trivial P
for (i=p*p;i<n;i*=p) // go through whole table
sieve[i]=p; // store P so it can be easily found later (if use 1bit/number then just set the bit instead)
}
return sieve[x];
}
- 第一个调用了
0.548毫秒
对矿井安装其他的都是非可测量小次 - 则返回
P
因此,如果点!= 0
的数量是在形式上P ^ Q
,所以你可以使用它作为布尔
直接,你也可以很容易地得到问:
通过分割,也可以创建问:
会更加快速,如果你还需要P,Q
- first call took
0.548 ms
on mine setup the others are non measurable small times - it returns the
P
so ifP!=0
the number is in formP^Q
so you can use it asbool
directly, and also you can easily getQ
by dividing or you can create another sieve withQ
to be even more fast if you need also theP,Q
在这里,都发现不平凡的力量 N'LT; 100000
Here all found non trivial powers 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毫秒
包括第一初始化调用(和字符串输出到备忘录是慢得多然后计算本身)没有它仅仅用了1.25毫秒
- it took
62.6 ms
including first init call (and string output to memo which is much slower then the computation itself) without the string it took just1.25 ms
这篇关于找到一个数是否为P ^ Q表格或没有?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!