Given a, b, c and k. Find the kth smallest positive number which is divisible by a or b or c.
Example 1:
Input: a = 1, b = 2, c = 3, k = 4
Output: 4
Explanation:
Sequence is 1, 2, 3, 4, 5…
Example 2:
Input: a = 2, b = 4, c = 5, k = 5
Output: 8
Explanation:
Sequence is 2, 4, 5, 6, 8, 10…
Example 3:
Input: a = 2, b = 3, c = 5, k = 10
Output: 14
Explanation:
Sequence is 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16…
Example 4:
Input: a = 3, b = 5, c = 7, k = 10
Output: 18
Constraints:
1<= T <=10^5
1<= a, b, c <=10^4
1<= k <=10^12
Time limit: 2 sec
贴下我的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL find_ans(LL a, LL b, LL c, LL k)
{
LL lcm_ab = (a*b)/__gcd(a,b);
LL lcm_ac = (a*c)/__gcd(a,c);
LL lcm_bc = (b*c)/__gcd(b,c);
LL lcm_abc = (a*b*c)/__gcd(__gcd(a,b),c);
LL kth = 0;
LL low = 1;
LL high = 1e17;
while(low <= high)
{
LL mid = (low+high)/2;
LL cnt = (mid/a) + (mid/b) + (mid/c) - (mid/lcm_ab) - (mid/lcm_ac) - (mid/lcm_bc) + (mid/lcm_abc);
if(cnt < k-1)
{
low = mid + 1;
}
else if(cnt > k-1)
{
high = mid - 1;
}
else
{
kth = mid;
break;
}
}
LL ans = min((kth/a+1)*a, min((kth/b+1)*b, (kth/c+1)*c));
return ans;
}
int main() {
LL a,b,c,k,t,ans;
cin>>t;
while(t--)
{
scanf("%lld %lld %lld %lld",&a,&b,&c,&k);
printf("%lld\n",find_ans(a,b,c,k));
}
return 0;
}