資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查給定形式的一個非常大的數字是否為 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 的和。
希望您在閱讀本文後已經理解了所有關於該問題的概念，並理解了解決該問題的演算法。
266 次瀏覽
