[BOJ] 1629번 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

코드

• C++ 17

#include <iostream>   using namespace std;   using ULL = unsigned long long;   ULL A, B, C;   // 빠른 모듈로 거듭제곱법을 사용한다. ULL Power(ULL a, ULL b, ULL c) {     if (b == 0)         return 1;       if (b == 1)         return a % c;       ULL temp = Power(a, b / 2, c);       if (b & 1)         return temp * temp % c * a % c;     else         return temp * temp % c; }   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);       cin >> A >> B >> C;     cout << Power(A, B, C); }

• C# 6.0

using System;   namespace ForAlgoCsharp {     class Program     {         static ulong A, B, C;           static void Main(string[] args)         {             string[] inputs = Console.ReadLine().Split();             A = Convert.ToUInt64(inputs[0]);             B = Convert.ToUInt64(inputs[1]);             C = Convert.ToUInt64(inputs[2]);             Console.Write(Power(A, B, C));         }                  static ulong Power(ulong a, ulong b, ulong c)         {             if (b == 0)                 return 1UL;             if (b == 1)                 return a % c;               ulong temp = Power(a, b / 2UL, c);               if (b % 2 == 1UL)                 return temp * temp % c * a % c;               return temp * temp % c;         }     } }

• Python 3

from sys import stdin input = stdin.readline   A, B, C = map(int, input().split())   def power(a, b, c):     if b == 0:         return 1     if b == 1:         return a % c       temp = power(a, b // 2, c)       if b & 1:         return temp * temp % c * a % c     return temp * temp % c   print(power(A, B, C))

복기

모듈로 연산에 관한 성질은 칸 아카데미에서 공부할 수 있다.