글 읽기 - 계속 시간초과가 납니다

ehoi710 3년 전 0

powmod에서 mulmod 함수를 쓰지 않으면 오버플로우로 무한루프에 들어가는 경우가 있고 mulmod를 쓰면 너무 느립니다. 어떻게 하면 해결할 수 있을까요?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>

typedef unsigned long long int ll;

inline ll gcd(ll x, ll y) {
	ll t;
	while(y) {
		t = x % y;
		x = y;
		y = t;
	}
	return x;
}

ll addmod(ll x, ll y, ll m) {
	x %= m;
	y %= m;
	return (x >= m - y ? x - (m - y) : x + y);
}

ll mulmod(ll x, ll y, ll m) {
	x %= m;
	y %= m;
	ll r = 0;
	while(y > 0) {
		if(y % 2 == 1)
			r = addmod(r, x, m);
		x = addmod(x, x, m);
		y /= 2;
	}
	return r;
}

ll powmod(ll x, ll y, ll m) {
	x %= m;
	ll r = 1;
	while(y > 0) {
		if(y % 2 == 1)
			r = mulmod(r, x, m);
		x = mulmod(x, x, m);
		y /= 2;
	}
	return r;
}

ll MillerRabin(ll n, ll a) {
	ll r = 0;
	ll i;
	ll d = n - 1;
	while(d % 2 == 0) {
		r += 1;
		d /= 2;
	}
	ll x = powmod(a, d, n);
	if(x == 1 || x == n - 1)
		return 1;
	
	for(i = 0; i < r; i++) {
		x = powmod(x, 2, n);
		if(x == n - 1) {
			return 1;
		}
	}
	return 0;
}

ll isPrime(ll n) {
	ll i;
	ll alist[] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
	
	if(n == 1) return 0;
	if(n == 2 || n == 3) return 1;
	if(n % 2 == 0) return 0;
	
	for(i = 0; i < 7; i++) {
		if(n == alist[i]) return 1;
		if(!MillerRabin(n, alist[i])) return 0;
	}
	return 1;
}

ll rho(ll n) {
	if(isPrime(n)) return n;
	if(n == 1) return 1;
	if(n % 2 == 0) return 2;
	
	ll x = (rand() % (n - 1)) + 2;
	ll y = x;
	ll c = (rand() % (n - 1)) + 1;
	ll d = 1;

	while(d == 1) {
		x = (powmod(x, 2, n) + c + n) % n;
		y = (powmod(y, 2, n) + c + n) % n;
		y = (powmod(y, 2, n) + c + n) % n;
		d = gcd((x-y > 0)?x-y:y-x, n);
		if(d == n) {
			return rho(n);
		}
	}
	if(isPrime(d))
		return d;
	else
		return rho(d);
}

int cmp(const void* a, const void* b) {
	if(*(ll*)a == *(ll*)b) return 0;
	if(*(ll*)a < *(ll*)b) return 1;
	if(*(ll*)a > *(ll*)b) return -1;
}

int main() {
	srand(time(NULL));
	ll Heap[64] = { 0, };
	int t = 0;
	int i;
	
	ll x, z;
	scanf("%lld", &x);
	while(x != 1) {
		z = rho(x);
		Heap[t] = z;
		t++;
		x /= z;
	}
	qsort(Heap, t, sizeof(ll), cmp);
	while(1) {
		z = Heap[--t];
		printf("%lld\n", z);
		if(t == 0) break;
	}
	return 0;
}

ehoi710 3년 전 0

__int128을 사용했음에도 시간초과가 발생하는 것으로 보아 그 점이 문제는 아닌 것 같습니다.

ehoi710 3년 전 0

소수 판별 함수의 문제 수정, 폴라드 로 함수에서의, 제대로 소인수 분해가 안되는 수열일 경우의 수열 재설정 등을 통해 문제를 해결했습니다.

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

문제

문제

출처

ICPC

계속 시간초과가 납니다

ehoi710 3년 전 0

ehoi710 3년 전 0

ehoi710 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말