讨论/面试考题/中国移动的坑货编程题,这题神仙能做?/
中国移动的坑货编程题,这题神仙能做?

Snipaste_2020-05-13_20-23-36.png
Snipaste_2020-05-13_20-23-56.png

展开讨论
共 5 个讨论

因数的个数是素数的等价条件我不知道怎么转化,但是如果一个数的因数个数是奇数,那么这个数一定是平方数,这个可以用来优化空间复杂度和时间复杂度,如果用素数筛来做的话,空间复杂度是O(N)O(\sqrt{N})

2

N的因子数量是奇数 -> N = a^2
对 a 质因数分解有 a = a1i1a2i2...anina_1^{i_1} * a_2^{i_2} *... * a_n^{i_n} , a1~an为互不相同的质数
则 N = a12i1a22i2...an2ina_1^{2i_1} * a_2^{2i_2} *... * a_n^{2i_n}
记N的因子数量为f(N)f(N)
f(N)f(N) = (2i1+1)(2i2+1)...(2in+1)(2i_1+1)*(2i_2+1)*...*(2i_n+1)
f(N)f(N) 为质数,则 n = 1 且 2i1i_1+1为质数
综上,若N的因子数量是奇数,则有 N=a2iN = a^{2i},其中aa为质数,2i+12i+1为质数
注意到a的上届是10^7,打个素数表遍历就行了

2

这有什么不能做的?很简单啊?
因数是奇素数
当且仅当它是素数的(奇素数-1)次方

数据范围在10^14次方
因此从2次方开始往上遍历
所有素数的2次方在AB之间的
所有素数的4次方在AB之间的
所有素数的6次方在AB之间的
所有素数的10次方在AB之间的
直到2^n大于B
div2 A-C 级别的题
就一点思维量 + 一点点代码量

等一下来写个证明和代码
我写的好像超时了,大概可以通过打表、二分什么的优化,但思路应该就是这样了,不想改了。

# region prime
# 素数模板

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        if n <= self._list[-1]: return
        maxbase = int(n ** 0.5) + 1
        self.extend(maxbase)
        begin = self._list[-1] + 1
        newsieve = [i for i in range(begin, n + 1)]
        for p in self.primerange(2, maxbase):
            for i in range(-begin % p, len(newsieve), p):
                newsieve[i] = 0
        self._list.extend([x for x in newsieve if x])
    def extend_to_no(self, i):
        while len(self._list) < i: 
            self.extend(int(self._list[-1] * 1.5))
    def primerange(self, a, b):
        a = max(2, a)
        if a >= b: return
        self.extend(b)
        i = self.search(a)[1]
        maxi = len(self._list) + 1
        while i < maxi:
            p = self._list[i - 1]
            if p < b:
                yield p
                i += 1
            else: return
    def search(self, n):
        if n < 2: raise ValueError
        if n > self._list[-1]: self.extend(n)
        b = bisect.bisect(self._list, n)
        if self._list[b - 1] == n: return b, b
        else: return b, b + 1
    def __contains__(self, n):
        if n < 2: raise ValueError
        if not n % 2: return n == 2
        a, b = self.search(n)
        return a == b
    def __getitem__(self, n):
        if isinstance(n, slice):
            if n.stop:
                self.extend_to_no(n.stop + 1)
                return self._list[n.start: n.stop: n.step]
            return islice(self, n.start, None)
        else:
            self.extend_to_no(n + 1)
            return self._list[n]
sieve = Sieve()

# endregion prime

# 上面是我的素数模板,平时打表也可以

def MP_Prime(A, B):
    if A > B:
        A, B = B, A
    t = 0
    for p in sieve[1:]:
        p -= 1
        if 2 ** p > B:
            break
        for b in sieve:
            if b ** p > B:
                break
            if b ** p >= A:
                t += 1
    return t

if __name__ == "__main__":
    print(MP_Prime(1, 10 ** 14))
2

直观地想,打表递归吧,记录每个数字的因数个数
我编不下去么

题目链接有吗?