CodeForces 448 E.Divisors（数论+递归）

60 阅读 0 评论 40 点赞

我是靠谱客的博主大方橘子，最近开发中收集的这篇文章主要介绍CodeForces 448 E.Divisors（数论+递归），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description
a是一个序列，f(a)表示把a中每个元素的所有因子从小到大排好构成一个新序列，现在给出一个整数n，X[1]=f(n)，X[i]=f(X[i-1])，求X[k]
Input
两个整数n和k(1<=n<=1e12,1<=k<=1e18)
Output
输出X[k]，如果X[k]的长度超过1e5则输出X[k]的前1e5项
Sample Input
10 3
Sample Output
1 1 1 2 1 1 5 1 1 2 1 5 1 2 5 10
Solution
如果把每个因子看作一个节点，该节点的儿子节点都是该因子的因子，根节点是n，那么问题其实是求这棵树的第k层的前1e5个节点，做法就是对该树前序遍历，这样就不要遍历完前k-1层才去遍历第k层，只要输出的数达到1e5后就不用遍历了，首先注意到如果k超过1e5那么前面全都是1，因为每次递归前面都会多一个1，故只需要考虑k<=1e5的情况，由于n的因子的因子还是n的因子，所以只需要求出n的所有因子，然后对于n的每个因子，从n的较小因子中找出能整除该因子的数即为该因子的所有因子，之后就直接递归去求X[k]的前1e5项，每次先从当前数的最小因子开始往下递归即可
Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 1111111
ll n,k,f[maxn];
vector<int>g[maxn];
int N=100000,tot;
void Solve(int pos,int k)
{
    if(tot>=N)return ;
    if(k==0)
    {
        printf("%I64d ",f[pos]);
        tot++;
        return ;
    }
    if(pos==0)
    {
        printf("1 ");
        tot++;
        return ;
    }
    for(int i=0;i<g[pos].size();i++)
    {
        Solve(g[pos][i],k-1);
        if(tot>=N)return ;
    }
}
int main()
{
    while(~scanf("%I64d%I64d",&n,&k))
    {
        if(k>=100000)
        {
            if(n==1)printf("1n");
            else
            { 
                for(int i=1;i<=N;i++)printf("1 ");
                printf("n");
            }
            continue;
        }
        tot=0;
        int res=0;
        for(ll i=1;i*i<=n;i++)
            if(n%i==0)
            {
                f[res++]=i;
                if(i*i!=n)f[res++]=n/i;
            }
        sort(f,f+res);
        for(int i=0;i<res;i++)
        {
            g[i].clear();
            for(int j=0;j<=i;j++)
                if(f[i]%f[j]==0)g[i].push_back(j);
        }
        Solve(res-1,k);
        printf("n"); 
    }
    return 0;
}