2016年1月26日 星期二

[Codeforces 448E]Divisors

用一般的$O(\sqrt{N})$的枚舉因數方法遞迴K層就可以了
不過有幾種重要的優化:
1. 如果$K>10^{5}$,直接輸出$10^{5}$個$1$,除非$X=1$
2. 如果在任何一層$X=1$,就直接輸出$1$,以防重複遞迴導致TLE
3. 將因數分解的結果記錄下來(可以用vector紀錄因數存在map裡面),以防超大質數的重複因數分解

時間複雜度:$O(\sqrt{X}\log X)$(質因數分解$\log X$個因數)

code:
#include<cstdio>
#include<cassert>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const LL bound=100000LL;
map<LL,vector<LL> >F;
void GetAnswer(const LL &h,const LL &x,LL &remain,vector<LL>&ans)
{
    if(remain==0LL)return;
    assert(remain>0LL);
    if(x==1LL||h==0LL){ans.push_back(x),remain--;return;}
    vector<LL>&f=F[x];
    if(f.empty())
    {
        vector<LL>stk;
        for(LL i=1LL;i*i<=x;i++)if(x%i==0LL)
        {
            f.push_back(i);
            if(i*i!=x)stk.push_back(x/i);
        }
        for(int i=(int)stk.size()-1;i>=0;i--)f.push_back(stk[i]);
    }
    for(const LL &v:f)GetAnswer(h-1LL,v,remain,ans);
}
LL X,K;
int main()
{
    while(scanf("%I64d%I64d",&X,&K)==2)
    {
        if(K>=100000)
        {
            putchar('1');
            if(X!=1LL)for(int i=1;i<100000;i++)printf(" 1");
            puts("");
        }
        else
        {
            LL remain=100000LL;
            vector<LL>ans;
            GetAnswer(K,X,remain,ans);
            for(int i=0;i<(int)ans.size();i++)
            {
                if(i)putchar(' ');
                printf("%I64d",ans[i]);
            }
            puts("");
        }
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原