摘要
Title: 1296. 聪明的燕姿
Tag: 约数的和、线性筛、DFS
Memory Limit: 64 MB
Time Limit: 2000 ms

1296. 聪明的燕姿

题意

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。
可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！
燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。
所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）。
可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。
思路

首先如果如果一个数的因数之和等于S，那么它一定能满足约数之和那个式子，所以可以看出其实很少的数能满足，可以采用爆搜的形式

先打出线性筛表，根据约数的和的形式，从小到大对素数进行爆搜，为了保证顺序，在搜的时候记录上一个搜的素数
最后搜到那个最大的，s - 1恰为质数时，(s - 1)就是质因子，写个函数判断即可

最后因为python太慢，一些重复的数据可以用字典进行记录，空间换时间

代码

'''
Author: NEFU AB-IN
Date: 2022-04-01 14:53:40
FilePath: \ACM\Acwing\1296.py
LastEditTime: 2022-04-01 14:56:07
'''
from copy import deepcopy
from collections import defaultdict

N = int(1e6 + 10)
st, primes = [0] * N, []
d = defaultdict(list)


def init():
    for i in range(2, N):
        if st[i] == 0:
            primes.append(i)
        j = 0
        while primes[j] * i < N:
            st[primes[j] * i] = 1
            if i % primes[j] == 0:
                break
            j += 1


def check(x):
    if x < N:
        return not st[x]
    i = 0
    while primes[i] <= x // primes[i]:
        if x % primes[i] == 0:
            return 0
        i += 1
    return 1


def dfs(last, prod, s):
    if s == 1:
        ans.append(prod)
        return
    if s - 1 > (1 if last < 0 else primes[last]) and check(s - 1):
        ans.append(prod * (s - 1))
    i = last + 1
    while primes[i] <= s // primes[i]:
        p = primes[i]
        j = 1 + p
        t = p
        while j <= s:
            if s % j == 0:
                dfs(i, prod * t, s // j)
            t *= p
            j += t
        i += 1


init()

while True:
    try:
        n = int(input())
        ans = []

        if d[n] != []:
            print(len(d[n]))
            if len(d[n]):
                d[n].sort()
                for i in d[n]:
                    print(i, end=" ")
                print()
            continue

        dfs(-1, 1, n)

        d[n] = deepcopy(ans)

        print(len(ans))
        if len(ans):
            ans.sort()
            for i in ans:
                print(i, end=" ")
            print()
    except:
        break

1296. 聪明的燕姿

题意

思路

代码