之江学院第0届 A qwb与支教容斥与二分

　　题目链接： http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=0

　　题目描述：给你三个数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

　　思考：自己还是太弱了，我尝试着去想，但是还是没想出来，其实这道题很容易往容斥那里去想的，毕竟都给出来了三个数，还是倍数题，二分也不难想，慢慢总结经验吧

之江学院第0届 A qwb与支教 容斥与二分

之江学院第0届 A qwb与支教容斥与二分