检查一个数字是否可以被41整除-yiteyi-C++库

给定一个数字，任务是快速检查该数字是否可被41整除。

null

例如：

Input : x  = 123Output : YesInput : 104413920565933Output : YES

这个问题的解决方案是提取最后一个数字，从剩余的数字中减去最后一个数字的4倍，然后重复这个过程，直到得到一个两位数。如果得到的两位数可以被41整除，那么给定的数字可以被41整除。 方法：

每次提取数字/截断数字的最后一位
从截断的数字中减去4*（上一个数字的最后一位）
根据需要重复上述三个步骤。

插图：

Illustration 1:30873-->3087-4*3=3075-->307-4*5=287-->28-4*7=0As the remainder is zero, 30873 is divisible by 41Illustration 2:104413920565933 --> 10441392056593 - 4*3= 1044139205658110441392056581 --> 1044139205658 - 4*1 = 10441392056541044139205654 --> 104413920565 - 4*4 = 104413920549104413920549 --> 10441392054 - 4*9 = 1044139201810441392018 --> 1044139201 - 4*8 = 10441391691044139169 --> 104413916 - 4*9 = 104413880104413880 --> 10441388 - 4*0 = 1044138010441388 --> 1044138 - 4*8 = 10441061044106 --> 104410 - 4*6 = 104386104386 --> 10438 - 4*6 = 1041410414 --> 1041 - 4*4 = 10251025 --> 102 - 4*5 =82Now, 82%41 = 0 --> 82 is divisible by 41 and hence, 104413920565933 is divisible by 41

数学证明： 允许

$overline{a b c}$

有多少这样的数字

$overline{a b c}$

=100a+10b+c。现在假设

$overline{a b c}$

可以被41整除。然后

$overline{a b c}equiv$

0（mod 41） 100a+10b+c

$equiv$

0（mod 41） 10（10a+b）+c

$equiv$

0（mod 41） 10

$overline{a b}$

+c

$equiv$

0（mod 41）现在我们已经把最后一个数字和数字分开了，我们必须找到一种使用它的方法。使系数

$overline{a b}$

1. 换句话说，我们必须找到一个整数，这样n，这样10n

$equiv$

1 mod 41。可以观察到，满足这个性质的最小n是-4as-40

$equiv$

1 mod 41。现在我们可以把原来的方程式乘以10

$overline{a b}$

+c

$equiv$

0（mod 41）通过-4并简化它： -40

$overline{a b}$

-4c

$equiv$

0（mod 41）

$overline{a b}$

-4c

$equiv$

0（mod 41）我们发现如果

$overline{a b c}equiv$

0（mod 41）那么，

$overline{a b}$

-4c

$equiv$

0（mod 41）。换句话说，要检查一个3位数是否可以被41整除，我们可以去掉最后一个数字，乘以4，然后从剩下的两位数中减去。

以下是上述方法的实施情况：

C++

                         // CPP program to validate above logic                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to check if the number                       
                         // is divisible by 41 or not                       
                         bool                                     isDivisible(                                     long                                     long                                     int                                     n)                       
                         {                       
                                                 while                                     (n / 100)                       
                                                 {                       
                                                 // Extracting the last digit                       
                                                 int                                     d = n % 10;                       
           
                                                 // Truncating the number                       
                                                 n /= 10;                       
           
                                                 // Subtracting the four times                       
                                                 // the last digit from the                       
                                                 // remaining number                       
                                                 n -= d * 4;                       
                                                 }                       
           
                                                 // return true if number is divisible by 41                       
                                                 return                                     (n % 41 == 0);                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 long                                     long                                     int                                     n = 104413920565933;                       
                                                 if                                     (isDivisible(n))                       
                                                 cout <<                                     "Yes"                                     << endl;                       
                                                 else                       
                                                 cout <<                                     "No"                                     << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to validate above logic                       
           
                         class                                     GFG {                       
           
                         // Function to check if the number                       
                         // is divisible by 41 or not                       
                                                 static                                     boolean                                     isDivisible(                                     long                                     n) {                       
                                                 while                                     (n /                                     100                                     !=                                     0                                     ) {                       
                         // Extracting the last digit                       
                                                 int                                     d = (                                     int                                     ) (n %                                     10                                     );                       
           
                         // Truncating the number                       
                                                 n /=                                     10                                     ;                       
           
                         // Subtracting the four times                       
                         // the last digit from the                       
                         // remaining number                       
                                                 n -= d *                                     4                                     ;                       
                                                 }                       
           
                         // return true if number                       
                         // is divisible by 41                       
                                                 return                                     (n %                                     41                                     ==                                     0                                     );                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 long                                     n = 104413920565933L;                       
                                                 if                                     (isDivisible(n)) {                       
                                                 System.out.println(                                     "Yes"                                     );                       
                                                 }                                     else                                     {                       
                                                 System.out.println(                                     "No"                                     );                       
                                                 }                       
           
                                                 }                       
                         }                       
                         // This code is contributed by RAJPUT-JI                       

Python3

                         # Python3 Program to validate above logic                       
           
                         # Function to check if the number                       
                         # is divisible by 41 or not                       
                         def                                     isDivisible(n) :                       
           
                                                 while                                     n                                     /                                     /                                     100                                     :                       
           
                                                 # Extracting the last digit                       
                                                 d                                     =                                     n                                     %                                     10                       
           
                                                 # Truncating the number                       
                                                 n                                     /                                     /                                     =                                     10                       
           
                                                 # Subtracting the four times                       
                                                 # the last digit from the                       
                                                 # remaining number                       
                                                 n                                     -                                     =                                     d                                     *                                     4                       
           
                                                 # return true if number is divisible by 41                       
                                                 return                                     n                                     %                                     41                                     =                                     =                                     0                       
                                   
           
                                   
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 n                                     =                                     104413920565933                       
                                   
                                                 if                                     isDivisible(n) :                       
                                                 print                                     (                                     "Yes"                                     )                       
           
                                                 else                                     :                       
                                                 print                                     (                                     "No"                                     )                       
                                   
                         # This code is contributed by ANKITRAI1                       

C#

                         // C# program to validate above logic                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         // Function to check if the number                       
                         // is divisible by 41 or not                       
                         static                                     bool                                     isDivisible(                                     long                                     n)                       
                         {                       
                                                 while                                     (n / 100 != 0)                       
                                                 {                       
                                                 // Extracting the last digit                       
                                                 int                                     d = (                                     int                                     )(n % 10);                       
           
                                                 // Truncating the number                       
                                                 n /= 10;                       
           
                                                 // Subtracting the four times                       
                                                 // the last digit from the                       
                                                 // remaining number                       
                                                 n -= d * 4;                       
                                                 }                       
           
                                                 // return true if number                       
                                                 // is divisible by 41                       
                                                 return                                     (n % 41 == 0);                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 long                                     n = 104413920565933;                       
                                                 if                                     (isDivisible(n))                       
                                                 Console.Write(                                     "Yes"                                     );                       
                                                 else                       
                                                 Console.Write(                                     "No"                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by Raj                       

PHP

                         <?php                       
                         // PHP program to validate above logic                       
           
                         // Function to check if the number                       
                         // is divisible by 41 or not                       
                         function                                     isDivisible(                                     $n                                     )                       
                         {                       
                                                 while                                     (                                     $n                                     / 100)                       
                                                 {                       
                                                 // Extracting the last digit                       
                                                 $d                                     =                                     $n                                     % 10;                       
           
                                                 // Truncating the number                       
                                                 $n                                     /= 10;                       
           
                                                 // Subtracting the four times                       
                                                 // the last digit from the                       
                                                 // remaining number                       
                                                 $n                                     -=                                     $d                                     * 4;                       
                                                 }                       
           
                                                 // return true if number                       
                                                 // is divisible by 41                       
                                                 return                                     (                                     $n                                     % 41 == 0);                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 104413920565933;                       
                         if                                     (isDivisible(                                     $n                                     ))                       
                                                 echo                                     "Yes"                                     .                                     ""                                     ;                       
                         else                       
                                                 echo                                     "No"                                     .                                     ""                                     ;                       
           
                         // This code is contributed                       
                         // by ChitraNayal                       
                         ?>                       

Javascript

                         <script>                       
                                   
                         // JavaScript program to validate above logic                       
           
                         // Function to check if the number                       
                         // is divisible by 41 or not                       
                                   
                                                 function                                     isDivisible(n)                       
                                                 {                       
                                                 while                                     (Math.floor(n / 100) != 0) {                       
                         // Extracting the last digit                       
                                                 let d =  (n % 10);                       
                                   
                         // Truncating the number                       
                                                 n = Math.floor(n/10);                       
                                   
                         // Subtracting the four times                       
                         // the last digit from the                       
                         // remaining number                       
                                                 n -= d * 4;                       
                                                 }                       
                                   
                         // return true if number                       
                         // is divisible by 41                       
                                                 return                                     (n % 41 == 0);                       
                                                 }                       
                                   
                                                 let n = 104413920565933;                       
                                                 if                                     (isDivisible(n)) {                       
                                                 document.write(                                     "Yes"                                     );                       
                                                 }                                     else                                     {                       
                                                 document.write(                                     "No"                                     );                       
                                                 }                       
                                   
           
                         // This code is contributed by avanitrachhadiya2155                       
           
                         </script>                       

输出：

Yes

请注意，上述程序可能没有多大意义，因为只需执行n%41即可检查整除性。这个项目的目的是验证这个概念。此外，如果输入数字较大且以字符串形式给出，这可能是一种有效的方法。

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

THE END

技术文章