AtCoder Beginner Contest 341 D - Only one of two (Java)
比赛链接:AtCoder Beginner Contest 341
D题传送门AtCoder:D - Only one of two
D题传送门洛谷:[ABC341D] Only one of two
题目:[ABC341D】 Only one of two
题目描述
输入格式
输入来自标准输入,格式如下:
N N N M M M K K K
输出格式
打印可被 N N N和 M M M之一整除的第 K K K个最小正整数。
样例 #1
样例输入 #1
2 3 5
样例输出 #1
9
样例 #2
样例输入 #2
1 2 3
样例输出 #2
5
样例 #3
样例输入 #3
100000000 99999999 10000000000
样例输出 #3
500000002500000000
分析:
由题目分析,暴力会超时,我们可以通过二分来解题。
我们需要找到第 K K K个被 N N N, M M M中一个整除的正整数。
我们知道: x / 2 = y . . z x / 2 = y .. z x/2=y..z 说明在 x x x时,有 y y y个数可以被 2 2 2整除
假设x是我们要找的数,c是a,b的最小公倍数。
我们可以计算出 x / a , x / b x/a ,x/b x/a,x/b,而c的倍数会被计算两次。
例如:a=4,b=6,则c=12;
如果x=24,x/a=6,x/b=4,x/c=2
出现个数:6+4-2*2=6,对应 4,6,8,12 ,16,18,20,24
即出现个数= x / a + x / b − 2 ∗ ( x / c ) x/a + x/b - 2*(x/c) x/a+x/b−2∗(x/c)
我们通过二分不断改变x的值,知道cnt与k相等。
代码:
import java.util.*;public class Main{// 最大公约数public static long gcd(long x,long y) {if(y==0) return x;return gcd(y,x%y);}public static void main(String[] args) { Scanner sc = new Scanner(System.in);long a = sc.nextLong();long b = sc.nextLong();long k = sc.nextLong();// c是a,b的最小公倍数long c = a*b/gcd(a,b);long cnt = 0;long l = 1;long r = Long.MAX_VALUE;// 二分左右边界while(l < r) {long mid = (l+r)/2;// 计算可被n和m中的一个整除的个数cnt =(mid/a)+(mid/b)-2*(mid/c);if(cnt<k) {l = mid+1;}else r = mid;}System.out.println(l);sc.close();}
}