878. the nth magic number math + two points

878. The first N A magic number

If a positive integer can be  a  or  b  to be divisible by , So it's amazing .

Given three integers  n , a , b , Back to page  n  A magic number . Because the answer can be big , So return the answer   Yes  109 + 7  modulus   After the value of .

Example 1：

 Input ：n = 1, a = 2, b = 3
 Output ：2

Example  2：

 Input ：n = 4, a = 2, b = 3
 Output ：6

Tips ：

• 1 <= n <= 10^9
• 2 <= a, b <= 4 * 10^4

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/nth-magical-number
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success  

Method ： mathematics + Two points

1. Find the greatest common divisor

2. Every time the greatest common divisor is reached , Namely from a The number of arrivals + from b Number of arrivals - lcm frequency

3. That's about the last common multiple , To the next common multiple , such as 6,2,3 ,2 and 3 The minimum common multiple is 6, Every time we arrive 6 Just pass 3 individual 2 Multiple and 2 individual 3 Multiple , among 6 It's public , Subtract 1 individual , Every time 6, Just consume 4 Number , So you can be sure ,n=6 It's through 1 individual Least common multiple period , That is to say n/4*6=6, That is, about 6 To 12 Between , You can get the answer in this part .

class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long lcm = lcm(a,b);
        long time = lcm/a+lcm/b-1;
        long left = n/time*lcm;
        long right = (n/time+1)*lcm;
        while(left<right){
            long mid = (right-left)/2+left;
            long cnt = mid/a+mid/b-mid/lcm;
            if(cnt<n){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return (int) (right%(long)(1e9+7));
    }

    private long lcm(long a, long b){
        long gcd = gcd(a,b);
        return a/gcd*b/gcd*gcd;
    }

    private long gcd(long a, long b){
        return b== 0?a:gcd(b,a%b);
    }
}

Time complexity ：O(log(max(a,b)))

Spatial complexity ：O(1)

other , If a,b smaller , n Large enough （ Intermediate calculation exceeds long） Under the circumstances , How to deal with it ？

Consider recording a cycle , Instead of counting the times directly , Front part , The sum of the remainder can be calculated directly to the common multiple , The last part can be reduced to the first cycle calculation , Then add the previous remainder to find the remainder .