반복 단위 분할성(C++ 사용)

이 글에서는 N으로 나누어지는 반복 단위의 수를 구하는 방법에 대해 논의하겠습니다. 반복 단위는 단순히 1의 반복 횟수입니다. R(k)를 반복 단위라고 가정합니다. 여기서 k는 1의 길이입니다. 예를 들어 R(4) = 1111입니다. 따라서 R(k)가 N으로 나누어지는 최소 k 수를 찾아야 합니다. -

Input : N = 13
Output : k = 6
Explanation : R(6) i.e 111111 is divisible by 13.

Input : N = 31
Output : k = 15

해를 찾는 방법

R(k)가 1인 곳에서 시작하여 k의 모든 값을 확인하면 이 문제를 해결할 수 있습니다. N으로 나눌 수 있나요? 그러나 이 솔루션을 사용하면 N이 R(k)의 값으로 나누어지는지 여부를 확인할 수 없습니다. 이렇게 하면 프로그램이 너무 복잡해지고 작동하지 않을 수도 있습니다.

이 프로그램을 해결하는 효율적인 방법은

• N이 10과 상대적으로 소수인지 확인하세요.
• 그렇지 않다면 R(k)는 어떤 k 값에 대해서도 N으로 나눌 수 없습니다.
• 그렇다면 각 반복 단위 R(1), R(2), R(3)...등에 대해 R(i)를 N으로 나눈 나머지를 계산하면 나머지가 n개가 됩니다.
• R(i)와 R(j)의 동일한 나머지를 찾으세요. 여기서 R(i)와 R(j)는 R(i) - R(j)가 N으로 나누어지는 두 개의 반복 단위입니다.
• aR (i)와 R(j)의 차이는 반복 단위에 10의 거듭제곱을 곱하지만 10과 N은 상대적으로 소수이므로 R(k)는 N으로 나눌 수 있습니다.

Example

#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;
}

Output

Value for k : 15

Conclusion

이 문서에서는 R(k)의 k 값을 찾는 방법에 대해 설명합니다. 여기서 R(k)는 주어진 N으로 나눌 수 있는 반복 단위입니다. 우리는 k 값을 찾는 낙관적인 접근 방식에 대해 논의했습니다. 이 문제를 해결하기 위해 C++ 코드에 대해서도 논의했습니다. 이 코드는 Java, C, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 반복 단위 분할성(C++ 사용)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!