检查给定形式的一个非常大的数字是否为 3 的倍数

---

问题陈述包括检查一个 K 位的非常大的正整数是否为 3 的倍数，其中 K 位数中的每一位 i（i>1）将是所有前缀数字模 10 的和。

我们将得到两个整数 a0 和 a1，其中 1<=a0<=9 且 0<=a1<=9，以及 K，它将是数字中的位数。a0 和 a1 是从左起数字的前两位。我们需要通过计算所有前缀数字模 10 的和来计算 K 位数，然后检查它是否为 3 的倍数。如果是 3 的倍数，则在输出中打印 yes，否则我们需要打印 no。

对所有前缀数字的和取模 10 是为了确保多位数的和。如果和是两位或多位数，我们只需要取和的最后一位，即数字的一位。

让我们通过以下示例了解问题陈述，这将有助于我们更好地理解问题。

示例

INPUT : a0=2, a1=3, K=5
OUTPUT : NO

说明 - 从数字的左边给出的前两位数字分别是 2 和 3。我们需要检查一个 5 位数，因为给定 K=5。形成的 5 位数，其中每一位都是所有前缀数字模 10 的和，是 23500。数字 a2=a1+a0=5，a3=a0+a1+a2=10 模 10=0。类似地，最后一位数字也是 0，使数字变为 23500，它不是 3 的倍数。因此，输出为 NO。

INPUT : a0=1, a1=5, K=6
OUTPUT : NO

说明 - 给出的前两位数字是 1 和 5，我们需要通过计算从左起所有前缀数字的模 10 和来找到 6 位数。形成的 6 位数将是 156248，它不是 3 的倍数，因此输出将为 NO。

a0 和 a1 的和是 6，使数字变为 156。

所有数字的和是 12，模 10 是 2，使数字变为 1562。

现在数字的和是 14，模 10 是 4，使数字变为 15624。

前缀数字的和是 18，模 10 是 8，使数字变为 156248。

由于形成的数字的位数为 6，等于 K，我们将检查它是否为 3 的倍数。

让我们了解通过计算从左起所有前缀数字的和来查找数字并检查它是否可被 3 整除的算法。

算法

在这个问题中，对于较大的 K 值，计算整个数字然后检查它是否可被 3 整除以知道数字是否为 3 的倍数可能需要很长时间。

解决该问题的算法指出，当数字计算为所有前缀数字模 10 的和时，它们在特定长度后开始重复。在本例中，数字以 4 的循环重复。前两位数字将在输入中给出，我们可以使用它们来找到第三位数字。在第三位数字之后，其余数字每四位重复一次。因此，我们可以简单地使用此逻辑计算 K 位整数以检查数字是否为 3 的倍数。

让我们通过示例了解算法。

假设我们得到 a0=1 和 a1=3 以及 K=11。K 位整数将是 13486248624。

在这里，我们可以看到数字从 a3 开始以 4 位的循环重复。

我们可以通过 a2=(a0+a1) mod 10 计算 a2。

数字 a3 可以写成 2 * (a0+a1) mod 10，方法是在表达式(a0+a1+a2) mod 10中替换 a2 的值。

数字 a4 可以写成 (a0+a1+a2+a3) mod 10 或 2 * (a0+a1) mod 10 + 2*(a0+a1) mod 10= 4 * (a0+a1) mod 10。

与前面的示例类似，a5=(a0+a1+a2+a3+a4) mod 10 = 8 * (a0+a1) mod 10，因为 a0+a1+a2+a3=a4，这使得 (2*a4) mod 10。

同样，a6=(a0+a1+a2+a3+a4+a5) mod 10 = (2 * a5) mod 10 = 16 * (a0+a1) mod 10 = 6*(a0+a1) mod 10。在这个表达式中，16 mod 10 可以写成 6。

如果我们计算数字的后续数字，则结果对于在最初三个数字之后以 4 位循环重复的数字是相同的。

通过计算 2 的幂模 10 乘以 a0 和 a1 的和（即 2）的模，即 2、4、8 和 6，可以识别数字中重复的数字。

因此，每个数字都是所有前缀数字模 10 的和的数字的总和可以通过以下公式给出：

Sum =a0+a1+a2+m*((K-3)/4)+n

其中，

m=以 4 为循环重复的数字的和。

(K-3)/4 = 给定数字中循环重复的次数

n = 未构成重复数字完整循环的剩余数字的和

在我们的方法中，我们将使用上述公式来计算 K 位数的数字之和，并检查它是否可被 3 整除，以解决问题。

方法

• 我们将创建一个布尔函数来检查数字是否为 3 的倍数。

• 为了检查给定数字是否为 3 的倍数，我们将找到数字的数字之和，并检查它是否可被 3 整除。

• 初始化一个变量以存储 m 的值，即以 4 为循环重复的数字的和。

• 然后使用 (K-3)%4 确定剩余的循环数字并将其存储在单独的变量中。由于前三个数字不是重复数字循环的一部分，因此使用 (K-3)。

• 我们将使用 switch case 来获取未完成重复数字循环的最后几位数字的和。如果只有两位数字剩余，我们将存储 2*(a0+a1) mod 10 和 4*(a0+a1) mod 10 的和到 n 中。类似地，根据剩余的数字，将存储关于 2 的幂模 10 重复循环的前两位数字的和与 2 的幂模 10 的乘积的和。

• 现在，我们使用公式计算 K 位整数的数字之和，并将结果存储在一个名为 sum 的变量中。

• 然后我们将检查 sum 是否可被 3 整除。如果它可被 3 整除，则打印 YES，因为它是 3 的倍数，否则打印 NO。

示例

该方法的 C++ 代码

//c++ code to check if the number is multiple of 3 

#include <bits/stdc++.h>
using namespace std;

//function to check if the sum of all digits of K sized integer is divisible by 3 or not
bool Multipleof3(int a0,int a1,long long int K) {
   //to calculate value of m in the formula
   long long int m=(2*(a0+a1))%10+(4*(a0+a1))%10+(8*(a0+a1))%10+(6*(a0+a1))%10;
   
   //to calculate the remaining terms of the repeating cycle of 4 digits
   long long int rem=(K-3)%4;
   
   //to store the sum of remaining digits
   long long int n;
   
   //using switch case to calculate sum of remaining digits
   switch(rem){
      case 0: //when remaining digit is 0
         n=0;
         break;
           
      case 1: //when remaining digit is 1
         n=(2*(a0+a1))%10;
         break;
           
      case 2: //when remaining digits are 2
         n=(2*(a0+a1))%10+(4*(a0+a1))%10;
         break;
           
      case 3: //when remaining digits are 3
         n=(2*(a0+a1))%10+(4*(a0+a1))%10+(8*(a0+a1))%10;
         break;
   }
   
   long long int a2=(a0+a1)%10; //calculating the third digit of the number from left
   
   //using the formula a0+a1+a2+m*((K-3)/4)+n, calculating the sum of all the digits
   long long int sum=a0 + a1 + a2 + ((K-3)/4)*m + n;
   
   if(sum%3==0){ //checking if sum is divisible by 3
      return true;
   } else {
      return false;
   }
}

int main()
{
   int a0, a1;
   long long int K; //initialising the input variables
   
   a0=7;
   a1=5;
   K=16;
   
   //checking if function returns true
   if(Multipleof3(a0,a1,K)==true){
      cout<<"Yes"<<endl;
   } else {
      cout<<"No"<<endl;
   }
   return 0;
}

输出

Yes

时间复杂度：O(1)，因为我们使用的算法在恒定时间内检查数字是否为 3 的倍数。

空间复杂度：O(1)，因为没有使用额外的空间来解决问题。

结论

本文讨论了计算任何 K 位整数的数字之和的方法，其中给出了从左起数字的前两位，并且每一位都是数字中所有前缀数字的和。使用高效的方法，我们可以在恒定时间和空间内用 C++ 解决检查数字是否为 3 的倍数的问题，其中每一位都是所有前缀数字模 10 的和。

希望您在阅读本文后已经理解了所有关于该问题的概念，并理解了解决该问题的算法。