Funcia
Lv.2divide-and-conquermath

거듭제곱의 나머지

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

질의 배열 queries가 주어집니다. 각 질의 queries[i] = [a, b, m]에 대해 aba^b를 m으로 나눈 나머지를 구해, 질의 순서대로 배열에 담아 반환하세요. 000^0은 1로 봅니다.

입출력 예

queriesresult
[[2, 10, 1000], [3, 0, 7], [10, 18, 7], [5, 3, 1]][24, 1, 1, 0]
[[7, 222, 13]][12]

입출력 예 설명

예 1 — 210=10242^{10} = 1024라 나머지는 24입니다. 30=13^0 = 1이고, 1018 mod 7=110^{18} \bmod 7 = 1입니다. 어떤 수든 1로 나눈 나머지는 0입니다.

예 2 — 72227^{222}은 매우 큰 수지만 나머지만 필요합니다. 지수는 최대 101810^{18}까지 커질 수 있습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(queries: long[][]) → long[]

제한 사항

  • 1≤1 \le queries.length ≤100,000\le 100{,}000
  • 0≤a≤1090 \le a \le 10^9, 0≤b≤10180 \le b \le 10^{18}, 1≤m≤1091 \le m \le 10^9

기대 복잡도

시간
O(Q log B)
공간
O(1)

입출력 예

queries기대 출력
[[2,10,1000],[3,0,7],[10,18,7],[5,3,1]][24,1,1,0]
[[7,222,13]][12]

힌트

힌트

분할 정복 거듭제곱(반복 제곱법)을 쓰세요. 지수를 2진수로 보면

a13=a8⋅a4⋅a1a^{13} = a^{8} \cdot a^{4} \cdot a^{1} (13 = 1101₂)

이므로 a를 계속 제곱하면서, 지수의 켜진 비트에서만 결과에 곱하면 됩니다. 곱셈 횟수는 log⁡2b≈60\log_2 b \approx 60번 정도입니다.

result = 1 % m;  base = a % m
while b > 0:
    if b & 1: result = result * base % m
    base = base * base % m
    b >>= 1

m이 10910^9 이하라 곱하기 전 두 수가 m 미만이면 곱이 101810^{18} 미만이어서 64비트 정수에 들어갑니다. 반드시 곱할 때마다 나머지를 취하세요. m = 1이면 답은 0이라 result = 1 % m으로 시작하는 것이 안전합니다.

복잡도 목표

a를 b번 곱하는 풀이는 b가 101810^{18}까지라 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)258 ms추정
C++ (GCC, gnu++23)258 ms도출됨
Python 3.131000 ms도출됨
Java 251638 ms도출됨
Kotlin 2.4 (JVM)1516 ms추정
C# 14 (.NET 10)1516 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness405판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.