首页 > 代码库 > 洛谷P2723 丑数 Humble Numbers [2017年 6月计划 数论07]
洛谷P2723 丑数 Humble Numbers [2017年 6月计划 数论07]
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个丑数。
输入输出样例
4 192 3 5 7
27
说明
题目翻译来自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]