题目
/problems/nth-magical-number/
题解
看了答案：
草稿：
class Solution {public static final long MOD = 1000_000_007;public int nthMagicalNumber(int n, int a, int b) {long L = lcm(a, b); // 最小公倍数long M = L / a + L / b - 1; // 循环周期long q = n / M; // 循环次数long r = n - M * q; // 余数int i = 0;long cur = (L * q) % MOD;int ai = a > b ? 0 : 1;int bi = 1 - ai;while (i <= r) {if (ai * a < bi * b) {cur = ((L * q) % MOD + ((long) ai * a) % MOD) % MOD;ai++;} else {cur = ((L * q) % MOD + ((long) bi * b) % MOD) % MOD;bi++;}i++;}return (int) cur;}// 最小公倍数static long lcm(int a, int b) {return (a / gcd(a, b)) * b;}// 最大公因数static long gcd(int a, int b) {if (a == 0) return b;return gcd(b % a, a);}}
