글 읽기 - 1629-곱셈 "틀렸습니다" 제곱근 이용하여 풀기

boffin 5년 전 0

왜 틀렸을까요 ㅠㅠㅠ흐아ㅏㅏㅏ

#include<cstdio>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>	
#include<algorithm>
#include<queue>
#include<math.h>
#include<stack>
using namespace std;

int A, B,B_mod, C;

int main() {
	cin >> A >> B >> C;
	int i=sqrt(B);
	B_mod = B % i;
	B = sqrt(B);

	long long int num = A;
	for (int i = 0; i < B; i++) {//제곱근 수만큼 제곱
		num *= A;
		num %= C;
	}
	num *= num;//제급근 수만큼 곱해진 수를 다시 제곱
	num %= C;

	for (int i = 0; i < B_mod; i++) {//나머지 수만큼 구해진 수에 기존A값 곱하기
		num *= A;
		num %= C;
	}
	cout << num%C;
}

hyunynim 5년 전 1

10 12 13

답:1 출력: 9

질문자께서 작성하신 코드의 경우

i = sqrt(B) = sqrt(12) = 3

B_mod = 12%3 = 0

B= sqrt(B) = 3 이 되므로, A의 4승을 구하고 이를 제곱하면 A의 8승이되고 나머지인 0번 곱하므로 A의 8승을 구하게 됩니다.

AC를 받은 코드에 10 8 13을 넣어보면 질문자께서 올려주신 코드에서 나오는 답인 9가 출력됩니다.

O(logN) 시간안에 A의 N승을 구하는 알고리즘은 유명하니 찾아보시면 좋으리라 생각됩니다!

boffin 5년 전 0

너무 감사드립니다!!!!!!으앗.....바보같았군요흐힣

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

문제

문제

출처

ICPC

1629-곱셈 "틀렸습니다" 제곱근 이용하여 풀기

boffin 5년 전 0

hyunynim 5년 전 1

boffin 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말