P4397 [JLOI2014]聪明的燕姿 题解

· · 题解

简要题意

不妨设一个数 x 的约数之和为 sum(x)，求所有满足 sum(x)=S 的数字。

\text{Solution}

前置芝士：线性筛，搜索

先介绍两条引理，分析时会用到。

由唯一分解定理可得，对于任意正整数 x，其可以被表示为

x=\prod_{i=1}^k(p_i^{a_i})

引理 1：

对于任意正整数 x，其约数个数为

\prod_{i=1}^k (a_i + 1)

引理 2：

对于任意正整数 x，其约数之和为

sum(x)=\prod_{i=1}^k\sum_{j=0}^{a_i} a_i^j

考虑暴力做法，枚举 [1,s] 内的数，枚举它们的约数，总时间 O(n\sqrt{n})，寄中寄。

考虑搜索解决，由于唯一分解定理，我们不妨通过决定每个质数的次数来获得每个数字以及其约数和。

对于边界条件，显然当约数之和剩余 1 时，当前的数字就是答案之一。

当当前剩余的约数之和是某个形如 (p_i^0 + p_i^1) 的形式时，我们只需要判断约数之和 -1（即 -p_i^0）是否为质数即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int N = 100010;
int s, cnt = 0, primes[N];
bool state[N];
vector<int>res;

inline void Euler(int n)
{
    memset(state, true, sizeof state);
    state[1] = false;
    for(int i(2);i <= n; ++ i)
    {
        if(state[i])
            primes[++ cnt] = i;
        for(int j(1);j <= cnt and 1ll * primes[j] * i <= n; ++ j)
        {
            state[i * primes[j]] = false;
            if(i % primes[j] == 0)
                break;
        }
    }
    return ;
}

inline bool is_prime(int x)
{
    if(x <= 100009)
        return state[x];
    for(int i(1);primes[i] <= x / primes[i]; ++ i)
        if(x % primes[i] == 0)
            return false;
    return true;
}

inline void dfs(int cur, int remain, int ret)
{
    if(remain == 1)
    {
        res.push_back(ret);
        return ;
    }
    if(remain > primes[cur] and is_prime(remain - 1))
        res.push_back(ret * (remain - 1));
    for(int i(cur);primes[i] <= remain / primes[i]; ++ i)
    {
        int sum = primes[i] + 1; // 当前选定质数的要乘上的约数和
        int t = primes[i]; // 当前数字乘上的质数是多少
        for(;sum <= remain;t *= primes[i], sum += t)
            if(remain % sum == 0)
                dfs(i + 1, remain / sum, ret * t);
    }
    return ;
}

signed main()
{
    Euler(N - 1);
    while(~scanf("%lld", &s))
    {
        dfs(1, s, 1);
        sort(res.begin(), res.end());
        if(!res.size())
            puts("0");
        else
        {
            printf("%lld\n", res.size());
            for(int i(0);i < res.size(); ++ i)
                printf("%lld ", res[i]);
            putchar('\n');
            res.clear();
        }
    }
    return 0;
}