03340网站建设与管理,wordpress美化登录界面,网站编程设计方向,小程序制作开发如意推题目链接#xff1a; http://115.231.222.240:8081/JudgeOnline/problem.php?cid1005pid0 题目描述#xff1a; 给你三个数x, y, z 和 N 输出从1开始数第N个不是x, y, z 任意一个数的倍数的数字 解题思路#xff1a; 一看到倍数我先想到素数唯一分解定理#xff0c; … 题目链接 http://115.231.222.240:8081/JudgeOnline/problem.php?cid1005pid0 题目描述 给你三个数x, y, z 和 N 输出从1开始数第N个不是x, y, z 任意一个数的倍数的数字 解题思路 一看到倍数我先想到素数唯一分解定理 但是这个想法不结合实际 因为N 10^17所以挨个遍历肯定是不切合实际的 然后我在想是不是可以可以素数筛法 更是不行。 于是上网上看了题解 既然不是倍数不好求 那么我就先求好求的倍数 ans mid/x mid/y mid/z - mid/lcm(x, y) - mid/lcm(y,z) - mid/lcm(x,z) mid/lcm(x,y,z) 其中ans 是 1 ~ ans 中是x, y, z的倍数的个数。 那么答案就应该是true_ans N mid 所以再二分就可以了。 这里有一个小小的trick 就是说lcm(x,y,z)有可能会爆longlong 特判一下即可。 代码 ps: 网站交不了题 这个代码只是思路的实现 并不是AC代码。 #include iostream
#include cstdio
#include cstring
#include algorithm
#include string
#include map
#include set
#include vector
#include cmath
using namespace std;typedef long long LL;
const LL MAXN 1e18;LL lcm(LL a, LL b) {LL GCD __gcd(a, b);LL ans a / GCD;if( MAXN / ans b ) return 0;else return ans * b;
}int main() {LL x, y, z, N;while( ~scanf(%lld%lld%lld%lld, x, y, z, N) ) {
// cout x y z N endl;LL left 0;LL right MAXN;while( left right-1 ) {
// cout left right endl;LL mid (left right) / 2;LL ans mid/x mid/y mid/z - mid/lcm(x, y) - mid/lcm(x, z) - mid/lcm(y, z);LL t lcm(lcm(x, y), z);if( t ) ans mid/t;if( mid - ans N ) {right mid;}else {left mid;}}printf( %lld\n, right );}return 0;
} View Code 思考 自己还是太弱了 我尝试着去想 但是还是没想出来 其实这道题很容易往容斥那里去想的 毕竟都给出来了三个数 还是倍数题 二分也不难想 慢慢总结经验吧 转载于:https://www.cnblogs.com/FriskyPuppy/p/7070425.html
