[백준/C++] 1629번 곱셈
2021. 4. 6. 19:25ㆍ알고리즘/재귀
728x90
반응형
문제: www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
문제풀이
재귀 함수를 이용하여 문제를 풀었다.
일반적인 반복문으로 풀면 a^b는 연산 횟수에 의한 시간초과나 a^b 값의 크기로 인한 오버플로우가 일어날 수 있다.
코드
#include <iostream>
using namespace std;
long long func(long long a, long long b, long long c){
if(b==1)
return a % c;
long long val = func(a,b/2,c);
val = val * val % c;
if(b%2==0){
return val;
}
else{
return val * a % c;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int a,b,c;
cin>>a>>b>>c;
cout<<func(a,b,c);
return 0;
}
결과
728x90
반응형
'알고리즘 > 재귀' 카테고리의 다른 글
[백준/C++] 2448번 별 찍기 - 11 (0) | 2021.04.28 |
---|---|
[백준/C++] 17478번 재귀함수가 뭔가요? (0) | 2021.04.27 |
[백준/C++] 2447번 별 찍기 - 10 (0) | 2021.04.27 |
[백준/C++] 1074번 Z (0) | 2021.04.09 |
[백준/C++] 11729 하노이 탑 이동 순서 (0) | 2021.04.07 |