Codeforces 448E Divisors - c++编程基础

TOP

Codeforces 448E Divisors

2015-07-20 18:04:27 来源: 作者: 【大中小】浏览:2次

数学型的题目吧，一开始太过于想去构造，发现不行，现在一直忙着补题，终于补到了这道，特意去看了后面很大的案例，发现了后面全是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-8 const 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); continue; } if(k >= 100000) { if(n == 1)puts(1); else { for(int i=1;i<=100000;i++) printf(%d%c,1,i == 100000?' ':' '); } continue; } int cnt = 0; for(ll i=0ll;i
                      
                       ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 1258 Agri-Net	下一篇：《C++ Primer Plus》学习笔记10

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: