글 읽기 - 반례 찾아주실분? ㅠㅠ

CicadaKim 4년 전 0

B가 홀수일때

A^B % C = ( (A^2) ^ (B/2) * A ) % C 이렇게 치환될수있을텐데요

B를 2로 계속 나눠서 지수가 1이될때까지 계속 반복해보면 답이 나올거라고 생각했는데, 답은 틀렸네요 ㅠㅠ

제 테스트 하에서는 아직 반례를 찾지 못했는데, 혹시 어떤 부분에서 틀린건지 알 수 있을까요?

감사합니다.

#include <iostream>

using namespace std;

typedef unsigned long long ullong;

ullong getSquareModulo(int A, int B, int C)
{
    if(B==0)
        return 1;
    if(B==1)
        return A % C;
    ullong last = B%2==1 ? A%C : 1;
    
    A = ((A%C) * (A%C)) % C;
    return (getSquareModulo(A,B/2,C) * last) % C;
}

int main()
{
    ullong A,B,C;
    
    cin>>A>>B>>C;
    
    ullong answer = getSquareModulo(A,B,C);
    cout<<answer<<endl;
    
    return 0;
}

wjsqjawns 4년 전 1

입력받을 때랑 출력하실 때에는 unsigned long long 타입으로 하시는데,

값을 parameter로 넘길 때에는 int 타입을 쓰시네요.

저것만 수정해주시면 정답 처리가 됩니다.

CicadaKim 4년 전 1

헉 그러네요 -/-

왜 몰랐지...

정말 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

반례 찾아주실분? ㅠㅠ

CicadaKim 4년 전 0

wjsqjawns 4년 전 1

CicadaKim 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말