Codeforces 448E Divisors-白红宇

Codeforces 448E Divisors

阅读量：5329 次

发布时间：2019-06-14

本文共 1763 字，大约阅读时间需要 5 分钟。

数学型的题目吧。一開始太过于想去构造。发现不行，如今一直忙着补题，最终补到了这道。特意去看了后面非常大的案例，发现了后面全是1。想想应该是数学思维型题目，对于1肯定要特殊处理，并且在K超过 100000的情况下肯定全为1，由于每一次 k从0開始 k若比原来大1的话，肯定答案中会比原来多一个1，所以10^5那肯定就有10^5个1 了，若k为0肯定就是n本身了，剩下的部分对于一開始就把n给分解。当然不须要素数分解，我没事吃饱了撑的想多了，直接分解就可以，细致观察那个f(x[i -1])慢慢的多谢几个，写个七八个就会发现得到的答案里的每一部分肯定是n的因子，仅仅是顺序有一定的问题，一開始分解的时候把全部因子排个序。然后由于f(x) 这个函数会一步一步的去再次分解n的因子而得到下一个答案。所以能够若大的因子能整除小的就加进去。最后就是输出处理的问题了。

可惜啊智商不够，处理了半天处理不了，他们所谓的“dfs树”问题。最后实在没办法參考了以为巨巨朋友做出来了，即便參考了还是写了非常久，好题目吧，收藏一下。以后脑子秀逗了回来看看做做

题目：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #define ll long long#define eps 1e-8const int inf = 0xfffffff;const ll INF = 1ll<<61;using namespace std;//vector
                  
                   
                     > G;//typedef pair
                    
                      P;//vector
                     
                      
                        > ::iterator iter;////map
                       
                        mp;//map
                        
                         ::iterator p;ll fac[1000000 + 5];ll n,k;ll tot = 0ll;vector
                         
                           G[1000000 + 5];void init() { for(ll i=1;i * i <= n;i++) { if(n%i == 0) { fac[tot++] = i; if(i * i != n) fac[tot++] = n / i; } } sort(fac,fac + tot);}int mark = 0;void dfs(ll pos,ll now) { if(mark >= 100000)return; if(pos == 0ll) { printf("1 "); mark++;return; } if(now == 0ll) { printf("%I64d ",fac[pos]); mark++;return ; } for(ll i=0ll;i
                          
                           = 100000 )return ; }}int main() { while(scanf("%I64d %I64d",&n,&k) == 2) { init(); if(k == 0) { printf("%I64d\n",n); continue; } if(k >= 100000) { if(n == 1)puts("1"); else { for(int i=1;i<=100000;i++) printf("%d%c",1,i == 100000?

'\n':' '); } continue; } int cnt = 0; for(ll i=0ll;i<tot;i++) { for(ll j=0ll;j<=i;j++) if(fac[i]%fac[j] == 0) { G[i].push_back(j); ++cnt; } } dfs(tot - 1,k); puts(""); } return 0; }

转载于:https://www.cnblogs.com/yangykaifa/p/6891272.html

你可能感兴趣的文章