首页 > 代码库 > Codeforces 448E Divisors

Codeforces 448E Divisors

数学型的题目吧。一開始太过于想去构造。发现不行,如今一直忙着补题,最终补到了这道。特意去看了后面非常大的案例,发现了后面全是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树”问题。最后实在没办法 參考了 以为巨巨朋友做出来了,即便參考了还是写了非常久,好题目吧,收藏一下。以后脑子秀逗了回来看看做做



题目: http://codeforces.com/contest/448/problem/E


#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

const int inf = 0xfffffff;

const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

ll fac[1000000 + 5];

ll n,k;

ll tot = 0ll;

vector<ll> 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<G[pos].size();i++) {
		dfs(G[pos][i],now - 1);
		if(mark >= 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; }



Codeforces 448E Divisors