【蓝桥杯冲冲冲】Prime Gift

【蓝桥杯冲冲冲】Prime Gift

蓝桥杯备赛 | 洛谷做题打卡day31

• Prime Gift

  题面翻译

  给你 $n$ 个互不相同的素数 $p_1,p_2,\cdots ,p_n$，它们组成一个集合 $P$。

  请你求出第 $k$ 小的正整数，满足：

  • 该数字的所有素因子 $\in P$

  $1\le n\le 16,2\le p_i\le 100,$ 保证答案不超过 $10^{18}$。

  题目描述

  Opposite to Grisha’s nice behavior, Oleg, though he has an entire year at his disposal, didn’t manage to learn how to solve number theory problems in the past year. That’s why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of $ n $ distinct prime numbers alongside with a simple task: Oleg is to find the $ k $ -th smallest integer, such that all its prime divisors are in this set.

  输入格式

  The first line contains a single integer $ n $ ( $ 1<=n<=16 $ ).

  The next line lists $ n $ distinct prime numbers $ p_{1},p_{2},…,p_{n} $ ( $ 2<=p_{i}<=100 $ ) in ascending order.

  The last line gives a single integer $ k $ ( $ 1<=k $ ). It is guaranteed that the $ k $ -th smallest integer such that all its prime divisors are in this set does not exceed $ 10^{18} $ .

  输出格式

  Print a single line featuring the $ k $ -th smallest integer. It’s guaranteed that the answer doesn’t exceed $ 10^{18} $ .

  样例 #1

  样例输入 #1

  3
  2 3 5
  7
  

  样例输出 #1

  8
  

  样例 #2

  样例输入 #2

  5
  3 7 11 13 31
  17
  

  样例输出 #2

  93
  

  提示

  The list of numbers with all prime divisors inside $ {2,3,5} $ begins as follows:

  $ (1,2,3,4,5,6,8,…) $

  The seventh number in this list ( $ 1 $ -indexed) is eight.

  

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define REP(a,b,c) for(int a=b;a<=c;a++)
int n,a[110],k;
LL A[5000010],B[5000010];
int lenA=0,lenB=0;
inline void dfs1(int x,LL s) {
	A[++lenA]=s;
	if (x>n) return ;
	for(LL i=1;;i*=a[x]) {
		if (1e18/i<s) break;
		dfs1(x+2,s*i);
	}
}
inline void dfs2(int x,LL s) {
	B[++lenB]=s;
	if (x>n) return ;
	for(LL i=1;;i*=a[x]) {
		if (1e18/i<s) break;
		dfs2(x+2,s*i);
	}
}
inline LL check(LL mid) {
	LL ans=0; int j=lenB;
	REP(i,1,lenA) {
		while (j>0&&B[j]>mid/A[i]) j--;
		ans+=1ll*j;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n; REP(i,1,n) cin>>a[i]; cin>>k;
	sort(a+1,a+n+1);
	dfs1(1,1); dfs2(2,1);
	LL l=0,r=1e18;
	sort(A+1,A+lenA+1);
	sort(B+1,B+lenB+1);
	lenA=unique(A+1,A+lenA+1)-A-1;
	lenB=unique(B+1,B+lenB+1)-B-1;
	while (l<r) {
		LL mid=(l+r)>>1;
		if (check(mid)>=k) r=mid;
		else l=mid+1;
	}
	cout<<r<<endl;
	return 0;
}//完结撒花! の_^

我的一些话

• 今天学习动态规划，dp属于比较难的部分，这题利用记忆化搜索即可快速解决，需要多动脑，多思考思路还是很好掌握的，虽然一次性AC有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o´ω`o)

• 如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔

• 总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）