Codeforces 448 E. Divisors (DFS,储存结构)

题意：

　　给出一个X，f(X)是X所有约数的数列（例6:1 2 3 6），给出一个k，k是递归的次数（例：k=2 : f(f(X)) ; X=4,k=2: 1 1 2 1 2 4 ）， X (1 ≤ X ≤ 10^12) and k (0 ≤ k ≤ 10^18)。现在给出X与k让你求这个序列，序列长度如果超过1e5就只存1e5个数。

题解：

　　这个题的话除了DFS没有想到特别好的方法，但是问题是强行DFS时间会超@。@。（DFS思路：处理出dfs时数的所有约数（n^1/2）最大是1e6的复杂度。深度最大是1e5：深度大于1e5其实就可以特判：如果N是1输出1，不然就输出1e5个1)。但是这样我们发现每次dfs都有处理约数复杂度太大，我们可以用map储存vector的方式。如果这个数以前已经被处理过就直接用，没处理过就处理后放到vector中再丢到map里面。（一定要用vector,在dfs中用静态数组好像很容易爆空间@。@）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAX_N = 3e5+9;
 4 vector<long long> vec;
 5 long long out[MAX_N];
 6 int num = 0;
 7 long long N,M,T;
 8 map< long long , vector<long long> > mp;
 9 void dfs(long long n,int pos)
10 {
11     if(num>=1e5) return;
12     vector <long long> vec;
13     if(mp.count(n)) vec = mp[n];
14     else
15     {
16         // vector 初始化
17         for(long long i=1;i*i<=n;i++)
18         {
19             if(n%i==0)
20             {
21                 vec.push_back(i);
22                 if(i != n/i) vec.push_back(n/i);
23             }
24         }
25         sort(vec.begin(),vec.end());
26         mp.insert(make_pair(n,vec));
27     }
28     if(pos == M)
29     {
30         for(int i=0;i<vec.size();i++)
31         {
32             out[num++] = vec[i];
33             if(num>=1e5) break;
34         }
35         return;
36     }
37     for(int i=0;i<vec.size();i++)
38     {
39         if(vec[i] == 1) out[num++] = 1;
40         else dfs(vec[i],pos+1);
41     }
42 }
43 int main()
44 {
45     while(cin>>N>>M)
46     {
47         mp.clear();
48         if(M==0)
49         {
50             printf("%lld
",N);
51             continue;
52         }
53         num = 0;
54 
55         if(M>=1e5)
56         {
57             if(N==1)
58                 printf("%lld
",N);
59             else
60                 for(int i=0;i<1e5;i++) printf("1 ");
61             continue;
62         }
63 
64         dfs(N,1);
65         for(int i=0;i<num;i++)
66         {
67             printf("%lld ",out[i]);
68         }
69         printf("
");
70     }
71     return 0;
72 }