ในบทความนี้ เราจะพูดถึงการหาจำนวนหน่วยที่ซ้ำกันหารด้วย N หน่วยที่ซ้ำกันคือจำนวนซ้ำของ 1 เท่านั้น ให้ R(k) เป็นหน่วยซ้ำ โดยที่ k คือความยาวของ 1 เช่น R(4) =1111 ดังนั้นเราต้องหาจำนวนขั้นต่ำของ k ที่ R(k) หารด้วย N ลงตัว ตัวอย่างเช่น −
Input : N = 13 Output : k = 6 Explanation : R(6) i.e 111111 is divisible by 13. Input : N = 31 Output : k = 15
แนวทางในการหาทางออก
คุณสามารถแก้ไขปัญหานี้ได้โดยการตรวจสอบแต่ละค่าของ k โดยเริ่มจาก 1 โดยที่ R(k) หารด้วย N ลงตัว แต่ด้วยวิธีแก้ปัญหานี้ เราจะไม่พบว่า N หารด้วยค่าของ R(k) ใดๆ ลงตัวหรือไม่ นี่จะทำให้โปรแกรมซับซ้อนเกินไปและอาจใช้งานไม่ได้เช่นกัน
แนวทางที่มีประสิทธิภาพสำหรับการแก้ปัญหาของโปรแกรมนี้คือ
- ตรวจสอบว่า N เป็น coprime กับ 10 หรือไม่
- ถ้าไม่ใช่ ดังนั้น R(k) จะไม่หารด้วย N สำหรับค่าใดๆ ของ k
- ถ้าใช่ ดังนั้นสำหรับแต่ละหน่วยที่ซ้ำกัน R(1), R(2), R(3)... และอื่นๆ ให้คำนวณส่วนที่เหลือของการหารของ R(i) และ N ดังนั้นจะมี n จำนวนส่วนที่เหลือ
- หาค่าที่เหลือเท่ากันสำหรับ R(i) และ R(j) โดยที่ R(i) และ R(j) เป็นหน่วยที่ซ้ำกันสองหน่วยเพื่อให้ R(i) - R(j) หารด้วย N
- aผลต่างของ R(i) และ R(j) จะถูกทำซ้ำหน่วยคูณด้วยกำลัง 10 แต่ 10 และ N เป็นจำนวนเฉพาะ ดังนั้น R(k) จะหารด้วย N.
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main() {
int N = 31;
int k = 1;
// checking if N is coprime with 10.
if (N % 2 == 0 || N % 5 == 0){
k = 0;
} else {
int r = 1;
int power = 1;
// check until the remainder is divisible by N.
while (r % N != 0) {
k++;
power = power * 10 % N;
r = (r + power) % N;
}
}
cout << "Value for k : "<< k;
return 0;
}
ผลลัพธ์
Value for k : 15
บทสรุป
ในบทความนี้ เราจะพูดถึงการหาค่าของ k สำหรับ R(k) โดยที่ R(k) เป็นหน่วยที่ซ้ำกันที่หารด้วย N ได้ เราพูดถึงวิธีคิดในแง่ดีในการหาค่าของ k นอกจากนี้เรายังกล่าวถึงรหัส C ++ เพื่อแก้ปัญหานี้ คุณสามารถเขียนโค้ดนี้ในภาษาอื่นๆ เช่น Java, C, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
