Project Euler 266

发表于 更新于 分类于 阅读次数： 本文字数： 665 阅读时长 ≈ 1 分钟

Project Euler 266

题目

Pseudo Square Root

The divisors of \(12\) are: \(1,2,3,4,6\) and \(12\).

The largest divisor of \(12\) that does not exceed the square root of \(12\) is \(3\).

We shall call the largest divisor of an integer \(n\) that does not exceed the square root of \(n\) the pseudo square root (\(\text{PSR}\)) of \(n\).

It can be seen that \(\text{PSR}(3102)=47\).

Let \(p\) be the product of the primes below \(190\). Find \(\text{PSR}(p) \bmod 10^{16}\).

解决方案

质数的个数只有\(m=42\)个，比较容易想到meet-in-the-middle思想。

令\(n\)为这些质数的积。前\(21\)个质数可以产生\(n\)的因子的一部分，存放在数组\(lm\)中，后\(21\)个质数也可以产生\(n\)的因子的另一部分，放在数组\(rm\)中。

那么，\(lm,rm\)中任意一对数的乘积组合就一一对应了\(n\)的因子。

因此在\(lm\)中，每遍历一个数\(x\)，就在\(rm\)中找到一个最大的\(y\)，使得\(xy\le \sqrt{N}\)。

采用排序后用双指针进行遍历的方法就可以完成这个问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from tools import int_sqrt, get_prime

N = 190
mod = 10 ** 16
pr = get_prime(N)
lm, rm = [1], [1]
for p in pr[:len(pr) >> 1]:
    lm += [x * p for x in lm]
for p in pr[len(pr) >> 1:]:
    rm += [x * p for x in rm]
sq = int_sqrt(lm[-1] * rm[-1])
lm.sort()
rm.sort()
r = len(rm) - 1
ans = 0
for l in range(len(lm)):
    while r >= 0 and lm[l] * rm[r] > sq:
        r -= 1
    if r < 0:
        break
    ans = max(ans, lm[l] * rm[r])
ans %= mod
print(ans)