글 읽기 - 이거 D&C 연습하려고 하는데 왜 이러는 걸까요..?

dohoon 3년 전 0

~~자꾸 틀렸다네요ㅠㅠ~~

~~나머지 연산도 꼼꼼히 했는데??ㅠㅠ~~

~~wolframalpha로 큰 수들도 여럿 검토해 봤는데 다 맞네요ㅠㅠㅠ~~

~~어디 간단한 실수를 했나봅니다...~~

~~문제점 좀 지적해주세요~~

~~아 그리고 D&C 처음이라서, 코드가 이상하면 알려주세용!~~

결국 이 문제는 풀어냈습니다!

하지만, 그 원인이 나머지가 음수이기 때문이였는데 그 점이 도저히 이해가 되지 않습니다.

뺄셈 연산 자체가 존재하지를 않는데 어떻게 음수가 나올 수 있는거죠..?

#include <iostream>
typedef long long ll;
ll A, B, C;

ll DnC (ll n) {
    if (n == 1) return A;
    ll x = DnC(n/2); x = (x*x)%C;
    if (n%2) return (x*A)%C;
    else return x;
}

int main() {
    std::cin >> A >> B >> C; A %= C;
    std::cout << DnC(B)%C;
}

clock 2년 전 0

오버플로우가 일어나서 부호비트를 건드리는 바람에 음수가 나온건 아닐까 조심스럽게 추측해 봅니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이거 D&C 연습하려고 하는데 왜 이러는 걸까요..?

dohoon 3년 전 0

clock 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말