ps:problems:boj:12728
n제곱 계산
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 12728 |
| 문제명 | n제곱 계산 |
| 레벨 | 플래티넘 1 |
| 분류 |
수학 |
| 시간복잡도 | O(Tlogn) |
| 인풋사이즈 | T<=100, n<=2*10^9 |
| 사용한 언어 | Python |
| 제출기록 | 30860KB / 108ms |
| 최고기록 | 64ms |
| 해결날짜 | 2022/01/30 |
풀이
- Numbers와 동일한 문제. 풀이는 그쪽 참고
코드
"""Solution code for "BOJ 12925. Numbers".
- Problem link: https://www.acmicpc.net/problem/12925
- Solution link: http://www.teferi.net/ps/problems/boj/12925
Tags: [Math]
"""
from teflib import combinatorics
MOD = 1000
COEF = [6, -4] # A(n)=6A(n-1)-4A(n-2) ( A(n) = (3+sqrt(5))^n + (3-sqrt(5))^n )
SEED = [2, 6] # A(0)=2, A(1)=6
def main():
T = int(input())
for i in range(T):
n = int(input())
answer = combinatorics.linear_homogeneous_recurrence(
COEF, SEED, n, MOD) - 1
print(f'Case #{i + 1}: {answer:>03}')
if __name__ == '__main__':
main()ps/problems/boj/12728.txt · 마지막으로 수정됨: 2022/02/02 06:20 저자 teferi
토론