题目124：求有序根函数的第k个元素
Ordered radicalsThe radical of n, rad(n), is the product of the distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.
If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:
Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.
If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).
题目：
n 的根函数，rad(n)，定义为其所有不同质因子之积。例如，504 = 23 × 32 × 7，所以 rad(504) = 2 × 3 × 7 = 42。
如果我们对 1 ≤ n ≤ 10 计算 rad(n)，然后先根据 rad(n) 的值排序，如果 rad 值相同再根据 n 排序，我们得到：
令 E(k) 为排序之后的第 k 个 n 值，例如， E(4) = 8， E(6) = 9。
如果将 1 ≤ n ≤ 100000 的 rad(n) 按照上述方法排序，求 E(10000)。
解答：
#coding:utf-8
plist = []
primes = * 100000
primes, primes = False, False
for i, prime in enumerate(primes):
if prime:
for j in range(i * i, 100000, i):
primes = False
for i, prime in enumerate(primes):
if prime:
plist.append(i)
def rad(n):
rlist = []
for p in plist:
if n % p == 0:
rlist.append(p)
n //= p
if n < p:
break
s = 1
for e in rlist:
s *= e
return s
order = [(1,1)]
for i in range(2,100001):
order.append((rad(i),i))
order.sort()
print (order)
输出：
21417 //21417
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
struct stNode
{
int idx;
int r;
bool operator<(const stNode &n) const
{
if (r != n.r)
return (r < n.r);
else
return (idx < n.idx);
}
};
stNode np;
char cp;
int main(void)
{
memset(cp, 1, sizeof(cp));
for (int i = 1; i <= 100000; ++i)
{
np.idx = i;
np.r = 1;
}
cp = 0;
cp = 0;
for (int i = 2; i <= 317; ++i)
{
if (cp == 0)
continue;
for (int j = i * i; j <= 100000; j += i)
cp = 0;
}
for (int i = 2; i <= 100000; ++i)
{
if (cp == 1)
{
for (int j = i; j <= 100000; j += i)
np.r *= i;
}
}
sort(np, np + 100001);
cout << np.idx << endl;
return 0;
}
页:
[1]