1-N 질문 드립니다
안녕하세요 큰돌님 😀
1-N 백준 1629 문제에서 제공해주신 코드에
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b){
if(b == 1) return a % c;
ll ret = go(a, b / 2);
ret = (ret * ret) % c;
if(b % 2)ret = (ret * a)% c;
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> a >> b >> c;
cout << go(a, b) << "\n";
return 0;
}여기에서
if(b % 2)ret = (ret * a)% c;원래 공식에 대입하면 이 부분에 (ret * a % c) % c 가 들어오는 것이 맞지 않나요..? 어떻게 이렇게 되는지 궁금합니다 ㅜㅜ
go(2, 3) 이라고 할 때,
이렇게 되어서
if(b % 2)ret = (ret * a)% c;이 아니라,
if(b % 2)ret = (ret * (a % c))% c;가 된다고 생각했는데 설명해주시면 감사합니다..ㅜㅜ
다른 질문에 답변 달아주신 내용 확인해서 이해하였습니다~!!
답변 2
0
안녕하세요, 인프런 AI 인턴입니다. Clain님의 질문은 모듈러 연산의 성질과 관련된 것으로 보입니다. 질문에 언급된 코드 조각은 분할 정복을 이용하여 거듭제곱을 빠르게 계산하는 알고리즘의 한 부분입니다. 예로 든 if(b % 2)ret = (ret * a) % c; 부분은 핵심이 되는 재귀 호출의 결과인 ret에 a를 곱하고 모듈러 연산을 실행하는 구간입니다.
Clain님은 재귀 함수의 결과에 다시 모듈러 연산을 적용해야 하는지에 대해 질문하셨고, 해당 부분을 다음과 같이 수정할 것을 제안하셨습니다.
if(b % 2)ret = (ret * a % c) % c;
제공된 링크 중에서 이와 관련된 설명을 해주는 답변을 찾았습니다. 아래 링크는 비슷한 질문에 대한 강사님의 해설을 포함하고 있는데, 여기에서 모듈러 연산의 성질을 이해하는 데 도움이 될 것입니다.
이전 답변에서의 핵심적인 부분은 ret이 이미 % c의 결과로 나왔기 때문에 다시 모듈러 연산을 할 필요가 없다는 설명입니다. 즉, (ret * ret) % c에서 이미 ret이 % c를 통해서 나온 값이기 때문에 이 값을 다시 ret % c로 하여 연산할 필요가 없고, 곱셈 연산 후의 결과에 모듈러 연산을 적용하면 된다고 설명하고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다. 🙏
4-F 경우의 수 질문입니다.
0
22
2
코딩살구클럽 가입이 안됩니다.
0
46
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
39
1
교안 158페이지 문의드립니다
0
37
2
코딩살구클럽 관련 건의사항
0
90
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
38
1
진행 방법 질문드립니다!
0
72
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
61
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
300
2
백준 서비스 종료
9
912
1
sk 하이닉스 코테 대비
0
377
2
3-G 최댓값 질문
0
52
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
63
2
3-N 질문 있습니다.
0
68
2
학습방법
0
104
2
4-H 질문 있습니다 (코드 리뷰)
0
67
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
178
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
70
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
52
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
69
2
함수별 시간복잡도
0
75
2