给定一个大数的前两位数 数字1 和 数字2 .也给出了一个数字 C 以及实际大数的长度。使用以下公式计算大数的下n-2位 数字[i]=（数字[i-1]*c+数字[i-2]）%10 .任务是检查形成的数字是否可被41整除。 例如：
null
Input: digit1 = 1 , digit2 = 2 , c = 1 , n = 3Output: YESThe number formed is 123which is divisible by 41Input: digit1 = 1 , digit2 = 4 , c = 6 , n = 3 Output: NO
A. 幼稚的方法 就是使用给定的公式来形成数字。检查形成的数字是否可被41整除，或者是否不使用%运算符。但由于数量非常大，不可能存储这么多。 有效方法： 使用给定的公式计算所有数字，然后 联想的 财产 乘法 和 附加 用于检查它是否可被41整除。一个数字是否可被41整除意味着（数字%41）是否等于0。 设X是这样形成的大数，可以写成。
X=（数字[0]*10^n-1）+（数字[1]*10^n-2）+……+（数字[n-1]*10^0） X=（（（数字[0]*10+数字[1]）*10+数字[2]）*10+数字[3]）…）*10+数字[n-1] X%41=（（（（（（（（数字[0]*10+数字[1]）%41）*10+数字[2]）%41）*10+数字[3]）%41）.*10+数字[n-1]）%41
因此，在计算完所有数字后，将遵循以下算法：
- 将第一个数字初始化为 ans .
- 对所有n-1位进行迭代。
- 每次我都会计算ans th 一步一步 （ans*10+位[i]）%41 使用关联属性。
- 如果ans的最终值可被41 r整除，则检查ans的最终值。
以下是上述方法的实施情况。
C++
// C++ program to check a large number // divisible by 41 or not #include <bits/stdc++.h> using namespace std; // Check if a number is divisible by 41 or not bool DivisibleBy41( int first, int second, int c, int n) { // array to store all the digits int digit[n]; // base values digit[0] = first; digit[1] = second; // calculate remaining digits for ( int i = 2; i < n; i++) digit[i] = (digit[i - 1] * c + digit[i - 2]) % 10; // calculate answer int ans = digit[0]; for ( int i = 1; i < n; i++) ans = (ans * 10 + digit[i]) % 41; // check for divisibility if (ans % 41 == 0) return true ; else return false ; } // Driver Code int main() { int first = 1, second = 2, c = 1, n = 3; if (DivisibleBy41(first, second, c, n)) cout << "YES" ; else cout << "NO" ; return 0; } |
JAVA
// Java program to check // a large number divisible // by 41 or not import java.io.*; class GFG { // Check if a number is // divisible by 41 or not static boolean DivisibleBy41( int first, int second, int c, int n) { // array to store // all the digits int digit[] = new int [n]; // base values digit[ 0 ] = first; digit[ 1 ] = second; // calculate remaining // digits for ( int i = 2 ; i < n; i++) digit[i] = (digit[i - 1 ] * c + digit[i - 2 ]) % 10 ; // calculate answer int ans = digit[ 0 ]; for ( int i = 1 ; i < n; i++) ans = (ans * 10 + digit[i]) % 41 ; // check for // divisibility if (ans % 41 == 0 ) return true ; else return false ; } // Driver Code public static void main (String[] args) { int first = 1 , second = 2 , c = 1 , n = 3 ; if (DivisibleBy41(first, second, c, n)) System.out.println( "YES" ); else System.out.println( "NO" ); } } // This code is contributed // by akt_mit |
Python3
# Python3 program to check # a large number divisible # by 41 or not # Check if a number is # divisible by 41 or not def DivisibleBy41(first, second, c, n): # array to store # all the digits digit = [ 0 ] * n # base values digit[ 0 ] = first digit[ 1 ] = second # calculate remaining # digits for i in range ( 2 ,n): digit[i] = (digit[i - 1 ] * c + digit[i - 2 ]) % 10 # calculate answer ans = digit[ 0 ] for i in range ( 1 ,n): ans = (ans * 10 + digit[i]) % 41 # check for # divisibility if (ans % 41 = = 0 ): return True else : return False # Driver Code first = 1 second = 2 c = 1 n = 3 if (DivisibleBy41(first, second, c, n)): print ( "YES" ) else : print ( "NO" ) # This code is contributed # by Smita |
C#
// C# program to check // a large number divisible // by 41 or not using System; class GFG { // Check if a number is // divisible by 41 or not static bool DivisibleBy41( int first, int second, int c, int n) { // array to store // all the digits int []digit = new int [n]; // base values digit[0] = first; digit[1] = second; // calculate // remaining // digits for ( int i = 2; i < n; i++) digit[i] = (digit[i - 1] * c + digit[i - 2]) % 10; // calculate answer int ans = digit[0]; for ( int i = 1; i < n; i++) ans = (ans * 10 + digit[i]) % 41; // check for // divisibility if (ans % 41 == 0) return true ; else return false ; } // Driver Code public static void Main () { int first = 1, second = 2, c = 1, n = 3; if (DivisibleBy41(first, second, c, n)) Console.Write( "YES" ); else Console.Write( "NO" ); } } // This code is contributed // by Smita |
PHP
<?php // PHP program to check a // large number divisible // by 41 or not // Check if a number is // divisible by 41 or not function DivisibleBy41( $first , $second , $c , $n ) { // array to store // all the digits $digit [ $n ] = range(1, $n ); // base values $digit [0] = $first ; $digit [1] = $second ; // calculate remaining digits for ( $i = 2; $i < $n ; $i ++) $digit [ $i ] = ( $digit [ $i - 1] * $c + $digit [ $i - 2]) % 10; // calculate answer $ans = $digit [0]; for ( $i = 1; $i < $n ; $i ++) $ans = ( $ans * 10 + $digit [ $i ]) % 41; // check for divisibility if ( $ans % 41 == 0) return true; else return false; } // Driver Code $first = 1; $second = 2; $c = 1; $n = 3; if (DivisibleBy41( $first , $second , $c , $n )) echo "YES" ; else echo "NO" ; // This code is contributed by Mahadev. ?> |
Javascript
<script> // Javascript program to check // a large number divisible // by 41 or not // Check if a number is // divisible by 41 or not function DivisibleBy41(first, second, c, n) { // array to store // all the digits let digit = new Array(n).fill(0); // base values digit[0] = first; digit[1] = second; // calculate remaining // digits for (let i = 2; i < n; i++) digit[i] = (digit[i - 1] * c + digit[i - 2]) % 10; // calculate answer let ans = digit[0]; for (let i = 1; i < n; i++) ans = (ans * 10 + digit[i]) % 41; // check for // divisibility if (ans % 41 == 0) return true ; else return false ; } // driver program let first = 1, second = 2, c = 1, n = 3; if (DivisibleBy41(first, second, c, n)) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by susmitakundugoaldanga. </script> |
输出：
YES
时间复杂性： O（N） 辅助空间： O（N）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
