原题大意

qwb同时也是是之江学院的志愿者，暑期要前往周边地区支教，为了提高小学生的数学水平。她把小学生排成一排，从左至右从1开始依次往上报数。

玩完一轮后，他发现这个游戏太简单了。于是他选了3个不同的数x,y,z；从1依次往上开始报数，遇到x的倍数、y的倍数或z的倍数就跳过。如果x=2,y=3,z=5；第一名小学生报1，第2名得跳过2、3、4、5、6，报7；第3名得跳过8、9、10，报11。

那么问题来了，请你来计算，第N名学生报的数字是多少？

算法分析

二分+容斥原理，详见代码

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll x, y, z, n;
ll gcd(ll a, ll b){
    return b == 0?a:gcd(b, a%b);
}
ll lcm(ll a, ll b){
    return a*b/gcd(a,b);
}
ll check(ll w){
    return w/x+w/y+w/z-w/lcm(x,y)-w/lcm(x,z)-w/lcm(z,y)+w/lcm(lcm(x,y),z);
}
ll ans;
int main(){
    while(scanf("%lld%lld%lld%lld",&x, &y, &z, &n) != EOF){
        ll l = 1, r = 1e18;
        while(l<=r){
            ll m = (l+r)>>1;
            if(m - check(m) < n) l = m+1;
            else{
                ans = m;
                r = m-1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}