글 읽기 - 5615번 왜 시간초과인지 모르겠습니다

thdtjdals3 3년 전 1

백준에 있는 예시와 JOI 홈페이지(https://www.ioi-jp.org/joi/200...)에서 제공하는 케이스들 다 통과했습니다.

나름대로 밀러-라빈 판정법을 구현했는데, MAX의 값보다 커질 경우 오버플로우가 발생할 것 같아 O(logy) 곱셈을 쓰도록 했습니다.

이 방법에 문제가 있는 건가요?

게시판에 있는 S-x를 2x+1로 나눠보는 방법도 시험해봤는데, x를 하나씩 늘리는 방법 외엔 생각을 못했습니다.

어떤 부분을 보완하면 좋을까요??

#include <stdio.h>
#include <stdbool.h>

bool flag;
long long MAX = ((long long)1<<31); // 2^63 의 근사치
long long base_list[3] = {2, 7, 61}; // if n < 4,759,123,141

long long multiply_modular (long long x, long long y, long long M); // O(logy) 곱셈
long long power_modular (long long x, long long y, long long M); // O(logy * logy) 지수

bool miller_rabin_test (long long N);

int main() {
	int N, i, count = 0;
	scanf("%d", &N);
	long long T;
	for (i = 0; i < N; i++) {
		scanf("%lld", &T);
		if (miller_rabin_test (T+T+1)) {
			count++;
		}
	}
	printf("%d", count);
	return 0;
}

long long multiply_modular (long long x, long long y, long long M) {
	x %= M;
	y %= M;
	long long result = 0;
	while (y) {
		if (y & 1) {
			result = (result + x) % M;
		}
		x = (x + x) % M;
		y >>= 1;
	}
	return result;
}

long long power_modular (long long x, long long y, long long M) {
	x %= M;
	long long result = 1;
	while (y) {
		if (y & 1) {
			if (result >= MAX && x >= MAX) { // MAX보다 크다면 O(logy)곱셈
				result = multiply_modular (result, x, M);
			}
			else {
				result = (result * x) % M;
			}
		}
		if (x >= MAX) { // MAX보다 크다면 O(logy)곱셈
			x = multiply_modular (x, x, M);
		}
		else {
			x = (x * x) % M;
		}
		y >>= 1;
	}
	return result;
}

bool miller_rabin_test (long long N) {
    
	if (N == base_list[0] || N == base_list[1] || N == base_list[2]) { // 2, 7, 61
		return true;
	}
    
	int s = 0;
	long long d = N - 1;
	while (!(d & 1)) {
		d >>= 1;
		s++;
	}
    
	int i, j;
	for (i = 0; i < 3; i++) {
        
		flag = false;
        
		long long x = power_modular(base_list[i], d, N);
		if (x == 1 || x == N - 1) {
			continue;
		}
        
		for (j = 1; j < s; j++) {
			if (x >= MAX) { // MAX보다 크다면 O(logy) 곱셈
				x = multiply_modular (x, x, N);
			}
			else {
				x = (x*x) % N;
			}
            
			if (x == N - 1) {
				flag = true;
				break;
			}
		}
        
		if (flag) {
			continue;
		}
        
		return false;
	}
	return true;
}

thdtjdals3 3년 전 0

자료형을 일단 unsigned long long으로 싹 바꾸고 O(logy) 곱셈을 없앴더니 해결되는 것 같습니다

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

문제

문제

출처

ICPC

5615번 왜 시간초과인지 모르겠습니다

thdtjdals3 3년 전 1

thdtjdals3 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말