租赁服务器做电影网站,在建设局网站备案怎么弄,淘宝客网站如何做排名,一起来做网站【蓝桥杯冲冲冲】Prime Gift 蓝桥杯备赛 | 洛谷做题打卡day31 文章目录 蓝桥杯备赛 | 洛谷做题打卡day31Prime Gift题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示题解代码我的一些话 Prime Gift 题面翻译 给你 n n n 个…【蓝桥杯冲冲冲】Prime Gift 蓝桥杯备赛 | 洛谷做题打卡day31 文章目录 蓝桥杯备赛 | 洛谷做题打卡day31Prime Gift题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示题解代码我的一些话 Prime Gift 题面翻译 给你 n n n 个互不相同的素数 p 1 , p 2 , ⋯ , p n p_1,p_2,\cdots,p_n p1,p2,⋯,pn它们组成一个集合 P P P。 请你求出第 k k k 小的正整数满足 该数字的所有素因子 ∈ P \in P ∈P 1 ≤ n ≤ 16 , 2 ≤ p i ≤ 100 , 1\le n\le 16,2\le p_i\le 100, 1≤n≤16,2≤pi≤100, 保证答案不超过 1 0 18 10^{18} 1018。 题目描述 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 $ ( $ 1n16 $ ). The next line lists $ n $ distinct prime numbers $ p_{1},p_{2},…,p_{n} $ ( $ 2p_{i}100 $ ) in ascending order. The last line gives a single integer $ k $ ( $ 1k $ ). 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以下是题解代码 ~ #includebits/stdc.h
using namespace std;
typedef long long LL;
#define REP(a,b,c) for(int ab;ac;a)
int n,a[110],k;
LL A[5000010],B[5000010];
int lenA0,lenB0;
inline void dfs1(int x,LL s) {A[lenA]s;if (xn) return ;for(LL i1;;i*a[x]) {if (1e18/is) break;dfs1(x2,s*i);}
}
inline void dfs2(int x,LL s) {B[lenB]s;if (xn) return ;for(LL i1;;i*a[x]) {if (1e18/is) break;dfs2(x2,s*i);}
}
inline LL check(LL mid) {LL ans0; int jlenB;REP(i,1,lenA) {while (j0B[j]mid/A[i]) j--;ans1ll*j;}return ans;
}
int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cinn; REP(i,1,n) cina[i]; cink;sort(a1,an1);dfs1(1,1); dfs2(2,1);LL l0,r1e18;sort(A1,AlenA1);sort(B1,BlenB1);lenAunique(A1,AlenA1)-A-1;lenBunique(B1,BlenB1)-B-1;while (lr) {LL mid(lr)1;if (check(mid)k) rmid;else lmid1;}coutrendl;return 0;
}//完结撒花! の_^我的一些话 今天学习动态规划dp属于比较难的部分这题利用记忆化搜索即可快速解决需要多动脑多思考思路还是很好掌握的虽然一次性AC有一定难度需要通盘的考虑和理解以及扎实的数据结构基础才能独立写出AC代码。但无论难易大家都要持续做题保持题感喔一起坚持(o´ωo) 如果有非计算机专业的uu自学的话关于数据结构的网课推荐看b站上青岛大学王卓老师的课讲的很细致有不懂都可以私信我喔 总结来说思路很重要多想想多在草稿纸上画画用测试数据多调试debug后成功编译并运行出正确结果真的会感到很幸福 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识之前的博文我都有写欢迎大家关注我翻阅自取哦~ 不管什么都要坚持吧三天打鱼两天晒网无法形成肌肉记忆和做题思维该思考的时候一定不要懈怠今天就说这么多啦欢迎评论留言一起成长
