ICPC2018JiaozuoE Resistors in Parallel 高精度 数论

题意简化下就是，让你求出一个不超过n(1e100)，且不含平方因子的数。使其所有因子倒数和的倒数尽可能小是多少。

因为电阻并联，所以显然并联越多越好，每个电阻越小越好。我们可以猜出，最大的电阻一定是2*5*7....p这样一个从2开始的连续质数的成绩。其他电阻是这个电阻的因子。

但是需要到251这个质数，成绩才能覆盖1e100。怎么求这么多因子的和是一个问题，所以我们打表观察规律。

规律：

10

6=2*3

100

30=2*3*5

1000

210=2*3*5*7

因子和

1,1 2,3 6,12 30,72 210,576

分子： 1 2 6 30 210

             *2 *3 *5 *7（全是素数）

分母： 1 3 12 72 576

             *3 *4 *6 *8（为上面素数+1）

然后Python高精度一下就好了。记得结果求gcd。

 1 import math
 2 notprime = [False for i in range(0,1000)]
 3 notprime[0] = notprime[1] = True
 4 for i in range(2,1000):
 5     if notprime[i] == False:
 6         if (i > 1000 / i):
 7             continue
 8         for j in range(i * i,1000,i):
 9             notprime[j] = True
10 T = int(input())
11 for mi in range(0,T):
12     n = int(input())
13     if n == 1:
14         print("1/1")
15         continue
16     elif 2 <= n and n <= 5:
17         print("2/3")
18         continue
19     a = 1
20     b = 1
21     for i in range(2,1000):
22         if notprime[i] == False:
23             if a * i > n:
24                 t = math.gcd(a,b)
25                 a = a // t
26                 b = b // t
27                 print(str(a) + '/' + str(b))
28                 break
29             a = a * i
30             b = b * (i + 1)