计算给定范围内A或B的总除数-yiteyi-C++库

给定四个整数m，n，a，b。找出从m到n范围内有多少个整数可以被a整除或 B 例如：

null

Input: 3 11 2 3Output: 6Explanation:m = 3, n = 11, a = 2, b = 3There are total 6 numbers from 3 to 11 which are divisible by 2 or 3 i.e, 3, 4, 6, 8, 9, 10 Input: arr[] = {11, 1000000, 6, 35}Output: 190475

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 天真的方法 就是从m到n运行一个循环，并计算所有可被a或b整除的数。这种方法的时间复杂度为O（m–n），对于m的大值，它肯定会超时。一 有效的方法 就是使用简单的LCM和除法。

分 N 由a获得可被a整除的所有数字（1到n）的总数。
分 m-1 由a获得可被a整除的所有数字（1到m-1）的总数。
减去第1步和第2步的计数，得到m到n范围内的总除数。

现在我们有了给定范围内的a的除数总数。重复上述步骤计算“b”的总除数。将它们相加以获得除数“a”和“b”的总数。但可被a和b整除的数字是两倍。因此，为了消除这种歧义，我们可以使用a和b的LCM来计算可被“a”和“b”整除的总数。

查找“a”和“b”的LCM。
分 N 通过LCM获得可被“a”和“b”整除的数字计数（1到n）。
分 m-1 通过LCM获得可被“a”和“b”整除的数字计数（1到m-1）。
减去第2步和第3步的计数，得到“a”和“b”的总除数。

现在从之前的计算结果中减去这个结果，得到“a”或“b”的所有唯一因子的总数。

C++

                         // C++ program to count total divisors of 'a'                       
                         // or 'b' in a given range                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Utility function to find LCM of two numbers                       
                         int                                     FindLCM(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 return                                     (a * b) / __gcd(a, b);                       
                         }                       
           
                         // Function to calculate all divisors in given range                       
                         int                                     rangeDivisor(                                     int                                     m,                                     int                                     n,                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 // Find LCM of a and b                       
                                                 int                                     lcm = FindLCM(a, b);                       
           
                                                 int                                     a_divisor = n / a - (m - 1) / a;                       
                                                 int                                     b_divisor = n / b - (m - 1) / b;                       
           
                                                 // Find common divisor by using LCM                       
                                                 int                                     common_divisor = n / lcm - (m - 1) / lcm;                       
           
                                                 int                                     ans = a_divisor + b_divisor - common_divisor;                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     m = 3, n = 11, a = 2, b = 3;                       
                                                 cout << rangeDivisor(m, n, a, b) << endl;                       
           
                                                 m = 11, n = 1000000, a = 6, b = 35;                       
                                                 cout << rangeDivisor(m, n, a, b);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count total divisors of 'a'                       
                         // or 'b' in a given range                       
           
                         import                                     java.math.BigInteger;                       
           
                         class                                     Test                       
                         {                       
                                                 // Utility method to find LCM of two numbers                       
                                                 static                                     int                                     FindLCM(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 return                                     (a * b) /                                     new                                     BigInteger(a+                                     ""                                     ).gcd(                                     new                                     BigInteger(b+                                     ""                                     )).intValue();                       
                                                 }                       
                                   
                                                 // method to calculate all divisors in given range                       
                                                 static                                     int                                     rangeDivisor(                                     int                                     m,                                     int                                     n,                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 // Find LCM of a and b                       
                                                 int                                     lcm = FindLCM(a, b);                       
                                   
                                                 int                                     a_divisor = n / a - (m -                                     1                                     ) / a;                       
                                                 int                                     b_divisor = n / b - (m -                                     1                                     ) / b;                       
                                   
                                                 // Find common divisor by using LCM                       
                                                 int                                     common_divisor = n / lcm - (m -                                     1                                     ) / lcm;                       
                                   
                                                 int                                     ans = a_divisor + b_divisor - common_divisor;                       
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     m =                                     3                                     , n =                                     11                                     , a =                                     2                                     , b =                                     3                                     ;                       
                                                 System.out.println(rangeDivisor(m, n, a, b));                       
                                   
                                                 m =                                     11                                     ; n =                                     1000000                                     ; a =                                     6                                     ; b =                                     35                                     ;                       
                                                 System.out.println(rangeDivisor(m, n, a, b));                       
                                                 }                       
                         }                       

Python3

                         # python program to count total divisors                       
                         # of 'a' or 'b' in a given range                       
           
                         def                                     __gcd(x, y):                       
           
                                                 if                                     x > y:                       
                                                 small                                     =                                     y                       
                                                 else                                     :                       
                                                 small                                     =                                     x                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , small                                     +                                     1                                     ):                       
                                                 if                                     ((x                                     %                                     i                                     =                                     =                                     0                                     )                                     and                                     (y                                     %                                     i                                     =                                     =                                     0                                     )):                       
                                                 gcd                                     =                                     i                       
                                   
                                                 return                                     gcd                       
                                   
                         # Utility function to find LCM of two                       
                         # numbers                       
                         def                                     FindLCM(a, b):                       
                                                 return                                     (a                                     *                                     b)                                     /                                     __gcd(a, b);                       
           
           
                         # Function to calculate all divisors in                       
                         # given range                       
                         def                                     rangeDivisor(m, n, a, b):                       
                                   
                                                 # Find LCM of a and b                       
                                                 lcm                                     =                                     FindLCM(a, b)                       
           
                                                 a_divisor                                     =                                     int                                     ( n                                     /                                     a                                     -                                     (m                                     -                                     1                                     )                                     /                                     a)                       
                                                 b_divisor                                     =                                     int                                     (n                                     /                                     b                                     -                                     (m                                     -                                     1                                     )                                     /                                     b)                       
                                   
                                                 # Find common divisor by using LCM                       
                                                 common_divisor                                     =                                     int                                     ( n                                     /                                     lcm                                     -                                     (m                                     -                                     1                                     )                                     /                                     lcm)                       
           
                                                 ans                                     =                                     a_divisor                                     +                                     b_divisor                                     -                                     common_divisor                       
                                                 return                                     ans                       
           
                         # Driver code                       
                         m                                     =                                     3                       
                         n                                     =                                     11                       
                         a                                     =                                     2                       
                         b                                     =                                     3                                     ;                       
                         print                                     (rangeDivisor(m, n, a, b))                       
                         m                                     =                                     11                       
                         n                                     =                                     1000000                       
                         a                                     =                                     6                       
                         b                                     =                                     35                       
                         print                                     (rangeDivisor(m, n, a, b))                       
           
                         # This code is contributed by Sam007                       

C#

                         // C# program to count total divisors                       
                         // of 'a' or 'b' in a given range                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     GCD(                                     int                                     num1,                                     int                                     num2)                       
                                                 {                       
                                                 int                                     Remainder;                       
           
                                                 while                                     (num2 != 0)                       
                                                 {                       
                                                 Remainder = num1 % num2;                       
                                                 num1 = num2;                       
                                                 num2 = Remainder;                       
                                                 }                       
           
                                                 return                                     num1;                       
                                                 }                       
                                   
                                                 // Utility function to find LCM of                       
                                                 // two numbers                       
                                                 static                                     int                                     FindLCM(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 return                                     (a * b) / GCD(a, b);                       
                                                 }                       
                                   
                                                 // Function to calculate all divisors in given range                       
                                                 static                                     int                                     rangeDivisor(                                     int                                     m,                                     int                                     n,                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 // Find LCM of a and b                       
                                                 int                                     lcm = FindLCM(a, b);                       
                                   
                                                 int                                     a_divisor = n / a - (m - 1) / a;                       
                                                 int                                     b_divisor = n / b - (m - 1) / b;                       
                                   
                                                 // Find common divisor by using LCM                       
                                                 int                                     common_divisor = n / lcm - (m - 1) / lcm;                       
                                   
                                                 int                                     ans = a_divisor + b_divisor - common_divisor;                       
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     m = 3, n = 11, a = 2, b = 3;                       
                                                 Console.WriteLine(rangeDivisor(m, n, a, b));                       
           
                                                 m = 11;    n = 1000000;                       
                                                 a = 6; b = 35;                       
                                                 Console.WriteLine(rangeDivisor(m, n, a, b));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

PHP

                         <?php                       
                         // PHP program to count total                       
                         // divisors of 'a' or 'b' in                       
                         // a given range                       
           
                         function                                     gcd(                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 return                                     (                                     $a                                     %                                     $b                                     ) ?                       
                                                 gcd(                                     $b                                     ,                                     $a                                     %                                     $b                                     ) :                       
                                                 $b                                     ;                       
                         }                       
           
           
                         // Utility function to                       
                         // find LCM of two numbers                       
                         function                                     FindLCM(                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 return                                     (                                     $a                                     *                                     $b                                     ) / gcd(                                     $a                                     ,                                     $b                                     );                       
                         }                       
           
                         // Function to calculate                       
                         // all divisors in given range                       
                         function                                     rangeDivisor(                                     $m                                     ,                                     $n                                     ,                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 // Find LCM of a and b                       
                                                 $lcm                                     = FindLCM(                                     $a                                     ,                                     $b                                     );                       
           
                                                 $a_divisor                                     =                                     $n                                     /                                     $a                                     - (                                     $m                                     - 1) /                                     $a                                     ;                       
                                                 $b_divisor                                     =                                     $n                                     /                                     $b                                     - (                                     $m                                     - 1) /                                     $b                                     ;                       
           
                                                 // Find common divisor by using LCM                       
                                                 $common_divisor                                     =                                     $n                                     /                                     $lcm                                     -                       
                                                 (                                     $m                                     - 1) /                                     $lcm                                     ;                       
           
                                                 $ans                                     =                                     $a_divisor                                     +                                     $b_divisor                                     -                       
                                                 $common_divisor                                     ;                       
                                                 return                                     $ans                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $m                                     = 3;                       
                         $n                                     = 11;                       
                         $a                                     = 2;                       
                         $b                                     = 3;                       
                         print                                     (                                     ceil                                     (rangeDivisor(                                     $m                                     ,                                     $n                                     ,                                     $a                                     ,                                     $b                                     )));                       
                         echo                                     ""                                     ;                       
           
                         $m                                     = 11;                       
                         $n                                     = 1000000;                       
                         $a                                     = 6;                       
                         $b                                     = 35;                       
                         print                                     (                                     ceil                                     (rangeDivisor(                                     $m                                     ,                                     $n                                     ,                                     $a                                     ,                                     $b                                     )));                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // JavaScript program to count total divisors                       
                                                 // of 'a' or 'b' in a given range                       
                                   
                                                 function                                     GCD(num1, num2)                       
                                                 {                       
                                                 let Remainder;                       
                                   
                                                 while                                     (num2 != 0)                       
                                                 {                       
                                                 Remainder = num1 % num2;                       
                                                 num1 = num2;                       
                                                 num2 = Remainder;                       
                                                 }                       
                                   
                                                 return                                     num1;                       
                                                 }                       
                                   
                                                 // Utility function to find LCM of                       
                                                 // two numbers                       
                                                 function                                     FindLCM(a, b)                       
                                                 {                       
                                                 return                                     parseInt((a * b) / GCD(a, b), 10);                       
                                                 }                       
                                   
                                                 // Function to calculate all divisors in given range                       
                                                 function                                     rangeDivisor(m, n, a, b)                       
                                                 {                       
                                                 // Find LCM of a and b                       
                                                 let lcm = FindLCM(a, b);                       
                                   
                                                 let a_divisor = parseInt(n / a, 10) -                       
                                                 parseInt((m - 1) / a, 10);                       
                                   
                                                 let b_divisor = parseInt(n / b, 10) -                       
                                                 parseInt((m - 1) / b, 10);                       
                                   
                                                 // Find common divisor by using LCM                       
                                                 let common_divisor = parseInt(n / lcm, 10) -                       
                                                 parseInt((m - 1) / lcm, 10);                       
                                   
                                                 let ans = a_divisor + b_divisor - common_divisor;                       
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 let m = 3, n = 11, a = 2, b = 3;                       
                                                 document.write(rangeDivisor(m, n, a, b) +                                     "</br>"                                     );                       
           
                                                 m = 11;    n = 1000000;                       
                                                 a = 6; b = 35;                       
                                                 document.write(rangeDivisor(m, n, a, b));                       
                                   
                         </script>                       

输出：

时间复杂性： O（对数（最大（a，b）） 辅助空间： O（1）本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章