【每日一题Day35】LC878第N个神奇数字 | 二分查找 找规律 + 数学

第N个神奇数字【LC878】

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

好难好难

更新于2022/11/23
[为什么突然那么多人看 压力好大 那就快来把丑数系列都做了吧
丑数系列+神奇数字总结
如有错误 还请批评指正 ^ o ^]

找规律

首先是我自己的暴力思路，当然没通过…但是可以结合官方题解2找规律一起看看

• 思路：根据题意，我们需要找到第n个能被a或者b整除的数。暴力判断1~n*min(a,b)内有多少个神奇数，必然超时。

  如何优化搜索的过程？神奇数一定是a或者b的倍数，因此只需判断a和b的整数倍即可。从小到大搜索第count个神奇数[过了50个还是超时]

  • 首先考虑几种特殊情况，a为b的因数或者b为a的因数，此时第n个神奇数即为 n * 较小值
  • 然后使用两个指针记录curA、curB，记录a的整数倍和b的整数倍，并使用count计数
    • 如果curA < curB，那么第count个神奇数为curA，移动curA
    • 如果curA < curB，那么第count个神奇数为curA，移动curB
    • 如果curA == curB，那么第count个神奇数为curA即curB，curA和curB在该值重合，需同时移动curA和curB，count只计一次数

• 代码

  class Solution {
      public int nthMagicalNumber(int n, int a, int b) {
          int MOD = (int)1e9 + 7;
          if (a == b){
              return (int)((long)n * a % MOD);
          }else if (a % b == 0){
              return (int)((long)n * b % MOD);
          }else if (b % a == 0){
              return (int)((long)n * a % MOD);
          }
          long count = 0;
          long curA = a;
          long curB = b;
          long res = 0;
          while (count < n){                        
              if (curA < curB){// 此时第count个神奇数字是curA
                  count++;
                  res = curA;
                  curA += a;
              }else if (curA > curB){// 此时第count个神奇数字是curB
                  count++;
                  res = curB;
                  curB += b;
              }else {// curA和curB重合，计数，并同时移动curA和curB
                  count++;
                  res = curB;
                  curA += a;
                  curB += b;
              }                    
          }
          return (int)(res % MOD);
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33

  • 复杂度

    • 时间复杂度：$O(nm)$，m为min(a,b)
    • 空间复杂度：$O(1)$

• 找规律，再次优化搜索过程。

  • 设f(x)为小于等于x的神奇数个数，c为a和b的最小公倍数，那么
    $$f(x)=\lfloor \frac{x}{a}\rfloor +\lfloor \frac{x}{b}\rfloor -\lfloor \frac{x}{c}\rfloor$$

    $$f(x\ast c)=x\ast (\lfloor \frac{c}{a}\rfloor +\lfloor \frac{c}{b}\rfloor -1)=q\ast f(c)$$

  • 令小于等于$c$的神奇数个数$m=f(c)$

  • 由于最终结果res一定是最小公倍数c的整数倍或者其的后几个数，因此$res=c\ast q+num$

  • 因为不大于 $c\ast q$ 的「神奇数字」个数为$m\ast q$，所以我们只需要从 $c\ast q$往后搜第 r个「神奇数字」即可。

    所以$n$可以由$m$表示，$n=q\ast m+r$,其中$0\le r<m$，$q$为非负整数

    • 如果r==0，那么$c\ast (n/m)$即为结果
    • 如果r!=0，那么从res往后搜索r次即可

  class Solution {
      static final int MOD = 1000000007;
  
      public int nthMagicalNumber(int n, int a, int b) {
          int c = lcm(a, b);
          int m = c / a + c / b - 1;
          int r = n % m;
          int res = (int) ((long) c * (n / m) % MOD);
          if (r == 0) {
              return res;
          }
          int addA = a, addB = b;
          for (int i = 0; i <  r - 1; ++i) {
              if (addA < addB) {
                  addA += a;
              } else {
                  addB += b;
              }
          }
          return (res + Math.min(addA, addB) % MOD) % MOD;
      }
  
      public int lcm(int a, int b) {
          return a * b / gcd(a, b);
      }
  
      public int gcd(int a, int b) {
          return b != 0 ? gcd(b, a % b) : a;
      }
  }
  
  作者：力扣官方题解
  链接：https://leetcode.cn/problems/nth-magical-number/solutions/1983699/di-n-ge-shen-qi-shu-zi-by-leetcode-solut-6vyy/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35

  • 复杂度

    • 时间复杂度：$O(a+b)$
    • 空间复杂度：$O(1)$

二分查找+数学

• 思路：将问题**“第n个神奇数是x”转化为“小于等于x的神奇数有n个”**，由于x越大n一定越大，因此可以使用二分法查找一个神奇数小于等于n的区间(0,right]，最后返回右边界

• 实现

  • 计算区间内的神奇数个数：假设该区间内能被a整除的数的个数为$n_a$个，能被b整除的数的个数为$n_b$个，能同时被a和被b整除的数的个数为$n_c$个，那么神奇数个数为$n_a+n_b-n_c$

  • $n_a$和$n_b$的计算方法较简单：除法运算向下取整即可

  • $n_c$=该区间内能被a和b的最小公倍数整除的个数

    • 最小公倍数可以使用最小公约数gcd得到
      $$lcm(a,b)=\frac{ab}{gcd(a,b)}$$

    • 最小公约数用辗转相除法得到

  • 实现

  class Solution {
      private static final long MOD = (long) 1e9 + 7;
  
      public int nthMagicalNumber(int n, int a, int b) {
          long lcm = a / gcd(a, b) * b;
          long left = 0, right = (long) Math.max(a, b) * n; // 开区间 (left, right)
          while (left + 1 < right) { // 开区间不为空
              long mid = left + (right - left) / 2;
              if (mid / a + mid / b - mid / lcm >= n)// 神奇数个数大于等于n
                  right = mid; // 范围缩小到 (left, mid)
              else// 神奇数个数小于n
                  left = mid; // 范围缩小到 (mid, right)
          }
          return (int) (right % MOD);
      }
  
      private int gcd(int a, int b) {
          return b == 0 ? a : gcd(b, a % b);
      }
  }
  
  作者：灵茶山艾府
  链接：https://leetcode.cn/problems/nth-magical-number/solutions/1984641/er-fen-da-an-rong-chi-yuan-li-by-endless-9j34/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25

  • 复杂度

    • 时间复杂度：$O(nlog(m)$，m为min(a,b)
    • 空间复杂度：$O(1)$