题目124：求有序根函数的第k个元素

欧拉计划

Ordered radicals

The radical of n, rad(n), is the product of the distinct prime factors of n. For example, 504 = 2³ × 3² × 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 = 2³ × 3² × 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)。

jerryxjr1220

解答：

1. #coding:utf-8
   
2. plist = []
   
3. primes = [True] * 100000
   
4. primes[0], primes[1] = False, False
   
5. for i, prime in enumerate(primes):
   
6.     if prime:
   
7.         for j in range(i * i, 100000, i):
   
8.             primes[j] = False
   
9. for i, prime in enumerate(primes):
   
10.     if prime:
    
11.         plist.append(i)
    
12. def rad(n):
    
13.     rlist = []
    
14.     for p in plist:
    
15.         if n % p == 0:
    
16.             rlist.append(p)
    
17.             n //= p
    
18.         if n < p:
    
19.             break
    
20.     s = 1
    
21.     for e in rlist:
    
22.         s *= e
    
23.     return s
    
24. 
    
25. order = [(1,1)]
    
26. for i in range(2,100001):
    
27.     order.append((rad(i),i))
    
28. order.sort()
    
29. print (order[9999])

复制代码

输出：
21417

guosl

1. //21417
   
2. #include <iostream>
   
3. #include <cstring>
   
4. #include <cmath>
   
5. #include <algorithm>
   
6. using namespace std;
   
7. 
   
8. struct stNode
   
9. {
   
10.   int idx;
    
11.   int r;
    
12.   bool operator<(const stNode &n) const
    
13.   {
    
14.     if (r != n.r)
    
15.       return (r < n.r);
    
16.     else
    
17.       return (idx < n.idx);
    
18.   }
    
19. };
    
20. 
    
21. stNode np[100001];
    
22. char cp[100001];
    
23. 
    
24. int main(void)
    
25. {
    
26.   memset(cp, 1, sizeof(cp));
    
27.   for (int i = 1; i <= 100000; ++i)
    
28.   {
    
29.     np[i].idx = i;
    
30.     np[i].r = 1;
    
31.   }
    
32.   cp[0] = 0;
    
33.   cp[1] = 0;
    
34.   for (int i = 2; i <= 317; ++i)
    
35.   {
    
36.     if (cp[i] == 0)
    
37.       continue;
    
38.     for (int j = i * i; j <= 100000; j += i)
    
39.       cp[j] = 0;
    
40.   }
    
41.   for (int i = 2; i <= 100000; ++i)
    
42.   {
    
43.     if (cp[i] == 1)
    
44.     {
    
45.       for (int j = i; j <= 100000; j += i)
    
46.         np[j].r *= i;
    
47.     }
    
48.   }
    
49.   sort(np, np + 100001);
    
50.   cout << np[10000].idx << endl;
    
51.   return 0;
    
52. }

复制代码