C++에서 'a'가 매우 큰 곳에서 (a^b)%m 찾기

이 튜토리얼에서는 방정식(a ^b )%m 여기서 는 매우 큰 숫자입니다.

방정식(a ^b )%m=(a%m)*(a%m)...b_times. %m의 값을 찾은 다음 b번 곱하면 문제를 해결할 수 있습니다.

문제를 해결하는 단계를 살펴보겠습니다.

• 숫자 a, b, m을 초기화합니다.

• a%m을 찾는 함수를 작성하세요.

  • 숫자를 0으로 초기화합니다.

  • 문자열 형식의 숫자를 반복합니다.

  • 숫자에 마지막 숫자를 추가하세요.

  • 숫자 모듈로 숫자를 업데이트합니다.

• %m의 값을 가져옵니다.

• b번 반복하는 루프를 작성하십시오.

  • a%m을 곱하고 결과를 m으로 모듈화합니다.

• 결과를 인쇄하십시오.

예

코드를 봅시다.

#include<bits/stdc++.h>
using namespace std;
unsigned int aModm(string str, unsigned int mod) {
   unsigned int number = 0;
   for (unsigned int i = 0; i < str.length(); i++) {
      number = number * 10 + (str[i] - '0');
      number %= mod;
   }
   return number;
}
unsigned int aPowerBmodM(string &a, unsigned int b, unsigned int m) {
   unsigned int a_mod_m_result = aModm(a, m);
   unsigned int final_result = 1;
   for (unsigned int i = 0; i < b; i++) {
      final_result = (final_result * a_mod_m_result) % m;
   }
   return final_result;
}
int main() {
   string a = "123456789012345678901234567890123";
   unsigned int b = 3, m = 7;
   cout << aPowerBmodM(a, b, m) << endl;
   return 0;
}

출력

위의 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

1

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.