글 읽기 - 이거 비슷한문제 없을까요

ghkdiwl 3년 전 0

이 문제는 맞았는데 인풋값 범위 넓혔을때도 시간초과 안나게 다시 짜봤는데 값이 맞게출력되는지 확인하고싶어요..

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

알고리즘은 이거 참고해서 짰어요 ..

혹시 비슷한 다른문제 없을까요 ㅜㅜ

#include <iostream>
#include <vector>
#define MOD 10
using namespace std;

vector<int> v;
int dp[50];

void tobinary(int num) {
	int i = 0;
	while (num != 1) {
		if (num % 2 != 0) v.push_back(i);
		num /= 2;
		i++;
	}
	v.push_back(i);
}
//2진수 변환시 1이 있는곳의 인덱스
//ex) 11 = 1011 => 013

int calc(int a, int b) {//a^(2^b) % MOD 계산
	if (b == 0) {
		dp[b] = a % MOD;
		return dp[b];
	}//a^(2^0) = a => return a
    
	int temp = (calc(a, b - 1) % MOD); 
	dp[b] = (temp * temp) % MOD;
	return dp[b];
}

void init() {
	for (int i = 0; i < 50; i++) {
		dp[i] = 0;
	}
	v.clear();
}

int main() {

	int T;
	int a, b;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> a >> b;

		tobinary(b);//2진수변환
		calc(a, v.back());

		int temp = 1;
		for (int i = 0; i < v.size(); i++)
			temp = (temp*dp[v[i]]) % MOD;
        //벡터에 저장된 1이있는곳의 인덱스 이용해서 dp에 미리 계산해둔 값들 찾아서 계산

		if (temp == 0) cout << MOD << endl;
		else cout << temp << endl;
		init();
	}

}

surung9898 3년 전 1

https://www.acmicpc.net/proble...

당장 생각나는 건 이거군요

ghkdiwl 3년 전 0

감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

이거 비슷한문제 없을까요

ghkdiwl 3년 전 0

surung9898 3년 전 1

ghkdiwl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말