P2723 丑数 Humble Numbers

题目背景

对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(还有其它)。该集合被称为S集合的“丑数集合”。注意：我们认为1不是一个丑数。

题目描述

你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。所有答案可以用longint(32位整数)存储。

补充：丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第N个“丑数”就是在能由素数集合中的数相乘得来的（包括它本身）第n小的数。

输入输出格式

输入格式：

第 1 行: 二个被空格分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000.

第 2 行: K 个被空格分开的整数:集合S的元素

输出格式：

单独的一行，输出对于输入的S的第N个丑数。

输入输出样例

输入样例#1：

4 19

2 3 5 7

输出样例#1：

说明

题目翻译来自NOCOW。

USACO Training Section 3.1

我居然卡常卡过了！

嗯。。

一个方法是用二叉堆（非手写过不了的）

我们设第i个丑数是num[i]

我们用所有p去乘num[i]，把它们压到栈里面。弹出最小数就是num[i + 1]

为了防止重加入的丑数重复需要判断一下

这题因为空间开小了交了很多遍才过

#include <bits/stdc++.h>

inline void read(long long &x){x = 0;char ch = getchar();while(ch > '9' || ch < '0'){ch = getchar();}while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();}

inline long long max(long long a, long long b){return a > b ? a : b;}

inline long long min(long long a, long long b){return a > b ? b : a;}

inline void swap(long long &a, long long &b){long long tmp = a;a = b;b = tmp;}

const int INF = 0x3f3f3f3f;

const int MAXN = 100000 + 10;

const int MAXK = 200 + 10; 

long long p[MAXK],k,n;

long long heap[MAXN << 7];int cnt;

//小根堆

inline int down()//下滤

{

	int rank = 1;

	while(true)

	{

		int p;

		if((rank << 1) > cnt)break;

		if((rank << 1 | 1) > cnt)p =  rank << 1;

		else

		{

			if(heap[rank << 1] < heap[rank << 1 | 1])

				p = (rank << 1);

			else

				p = (rank << 1 | 1);

		}

		if(heap[rank] >= heap[p])

		{

			swap(heap[rank], heap[p]);

			rank = p;

		}

		else break;

	}

}

inline void up(int rank)//上滤

{

	while(heap[rank] < heap[rank >> 1] && rank > 1)

	{

		swap(heap[rank], heap[rank >> 1]);

		rank >>= 1;

	}

}

inline void insert(long long k)

{

	heap[++cnt] = k;

	up(cnt);

}

inline void del()

{

	swap(heap[1], heap[cnt]);

	cnt --;

	down();

}

long long ans[MAXN];long long num;

int main()

{

	read(k);read(n);

	for(int i = 1;i <= k;i ++)

	{

		read(p[i]);

	}

	heap[++cnt] = 1;

	while(num <= n)

	{

		int tmp = heap[1];del();

		if(ans[num] < tmp)

		{

			ans[++num] = tmp;

			for(int i = 1;i <= k;i ++)

			{

				insert(tmp * p[i]);

			}

		}

	}

	printf("%lld", ans[n + 1]);

	return 0;

}

另一种解法：

我们要找的ans[i] 要尽可能的接近ans[i - 1]

显然ans[i]是由素数集合p中某一个数与ans[j],j<i的乘积

证明：

令ans[i] = p[k] * M,k为任意数

如果M≠ans[j],则M < ans[j]

那么M一定会被计入到前j个丑数中

矛盾

这样我们定义s[i]表示用素数i乘ans[s[i]]最接近ans[i - 1]的ans下标s[i]

可以得到i - 1时的s[k] 一定小于等于i时的s[k],k取任意数

所以s[j]可以从i-1过继到i的，然后去递增直到满足 “s[i]表示用素数i乘ans[s[i]]最接近ans[i - 1]的ans下标s[i]”

#include <bits/stdc++.h>

inline void read(long long &x){x = 0;char ch = getchar();while(ch > '9' || ch < '0'){ch = getchar();}while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();}

inline long long max(long long a, long long b){return a > b ? a : b;}

inline long long min(long long a, long long b){return a > b ? b : a;}

inline void swap(long long &a, long long &b){long long tmp = a;a = b;b = tmp;}

const long long INF = 0xfffffffffffffff;

const int MAXN = 1000000 + 10;

const int MAXK = 2000 + 10; 

long long k,n,p[MAXK],ans[MAXN],s[MAXK];

int main()

{

	read(k);read(n);

	for(int i = 1;i <= k;i ++){

		read(p[i]);

	}

	ans[0] = 1;

	for(int i = 1;i <= n;i ++)

	{

		ans[i] = INF;

		for(int j = 1;j <= k;j ++)

		{

			while(p[j] * ans[s[j]] <= ans[i - 1])s[j] ++;

			ans[i] = min(ans[i], p[j] * ans[s[j]]);

		}

	}

	printf("%lld", ans[n]);

	return 0;

}

巴特西

洛谷P2723 丑数 Humble Numbers [2017年 6月计划数论07]

P2723 丑数 Humble Numbers

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

巴特西

洛谷P2723 丑数 Humble Numbers [2017年 6月计划 数论07]

P2723 丑数 Humble Numbers

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

洛谷P2723 丑数 Humble Numbers [2017年 6月计划数论07]