글 읽기 - 파이썬으로는 맞았는데 c++로 푸니까 시간초과가 납니다.

kimhs 2년 전 0

똑같은 로직으로 구현했는데 c++에서는 시간초과가 납니다.

혹시 vector를 처리하는 부분이 문제인 건가요?

#파이썬 (맞는 코드)
import random

primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71)

def g(x, c, num):
    return (x * x + c) % num

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def __isprime(num):
    if num == 1:
        return False
    d = num - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in primes:
        if a >= num:
            break
        passed = False
        if pow(a, d, num) == 1:
            passed = True
            continue
        for r in range(s):
            if pow(a, pow(2, r) * d, num) == num - 1:
                passed = True
                break
        if passed == False:
            return False
    return True

def pollard_rho(num):
    if __isprime(num):
        return [num]
    if num == 4:
        return [2, 2]
    while 1:
        c = random.randint(1, 9)
        x = random.randint(1, 9)
        y = x
        d = 1
        while d == 1:
            x = g(x, c, num)
            y = g(g(y, c, num), c, num)
            d = gcd(abs(x - y), num)
        if d == num:
            continue
        return pollard_rho(num // d) + pollard_rho(d)

n = int(input())
for i in sorted(pollard_rho(n)):
    print(i)

    
//c++ (틀린 코드)
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long int lld;

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};

lld g(lld x, int c, lld num);
lld gcd(lld a, lld b);
bool __isprime(lld num);
vector<lld> pollard_rho(lld num);
lld __pow(int a, lld n, lld mod);
lld __pow(int a, lld n);
lld __abs(lld num);

int main(){
    srand((unsigned)time(nullptr));

    lld n;
    cin >> n;

    vector<lld> divs = pollard_rho(n);

    sort(divs.begin(), divs.end());

    for(auto iter = divs.begin(); iter < divs.end(); iter++){
        printf("%lld\n", *iter);
    }

    return 0;
}

lld g(lld x, int c, lld num){
    return (x * x + c) % num;
}

lld gcd(lld a, lld b){
    while(b != 0){
        lld r = a % b;
        a = b;
        b = r;
    }
    return a;
}

bool __isprime(lld num){
    if(num == 1) return false;
    lld d = num - 1;
    int s = 0;
    while(d % 2 == 0){
        d >>= 1;
        s++;
    }
    for(int idx = 0; idx < 20; idx++){
        int a = primes[idx];
        if(a >= num) break;
        bool passed = false;
        if(__pow(a, d, num) == 1){
            passed = true;
            continue;
        }
        for(int r = 0; r < s; r++){
            if(__pow(a, __pow(2, r) * d, num) == num - 1){
                passed = true;
                break;
            }
        }
        if(passed == false) return false;
    }
    return true;
}

vector<lld> pollard_rho(lld num){
    if(__isprime(num)){
        vector<lld> res(1, num);
        return res;
    }
    if(num == 4){
        vector<lld> res(2, 2);
        return res;
    }
    while(true){
        int c = rand() % 9 + 1;
        lld x = rand() % 9 + 1;
        lld y = x;
        lld d = 1;
        while(d == 1){
            x = g(x, c, num);
            y = g(g(y, c, num), c , num);
            d = gcd(__abs(x - y), num);
        }
        if(d == num) continue;
        vector<lld> v1, v2;
        v1 = pollard_rho(num / d);
        v2 = pollard_rho(d);
        v1.insert(v1.end(), v2.begin(), v2.end());
        return v1;
    }

}

lld __pow(int a, lld n, lld mod){
    if(n == 0) return 1;
    lld res = __pow(a, n / 2, mod);
    res = res * res % mod;
    if(n & 1) res = res * a % mod;
    return res;
}

lld __pow(int a, lld n){
    if(n == 0) return 1;
    lld res = __pow(a, n / 2);
    res *= res;
    if(n & 1) res *= a;
    return res;
}

lld __abs(lld num){
    return (num < 0) ? -num : num;
}

ldhun041203 2년 전 1

저도 c++해서 못 푼 사람입니다.

매우 큰 숫자로 시도해보니 __int128을 사용해도 결과가 나오지 않았습니다. 입력 범위가 10^18이라 제곱을 하게 되면 overflow가 일어나는 것 같습니다. 전에 글 쓴 분께서는 플라드 로에서 루프가 생기는 부분을 해결했다고 하셨는데 저는 어떻게 하는지 잘 모르겠군요.

파이썬은 정수 크기가 제한이 무제한인 걸로 알고 있는데, 이 때문에 파이썬에서는 결과를 내주는 것 같습니다.

실제로 파이썬으로 실행해보니, c++과는 다르게 결과를 보여주더군요. (질문 글 중 테스트 케이스 모음 중 매우 큰 수를 이용했습니다.)

kimhs 2년 전 0

답변 감사합니다

오버플로 관련해서 좀 더 생각해봐야겠네요.

yup0927 2년 전 1

입력으로 큰 수들을 넣었을 때 답이 나오지가 않습니다.

(4611686018427387903, 4611686018427387902, 4611686018427387901, 4611686018427387899 등)

__int128로 바꿨을 때 일단 무한 루프를 도는 것 같지는 않습니다.

저 같은 경우에는 밀러 라빈과 거듭제곱에서 오버플로우가 나면서 무한 루프를 돌아 TLE가 나서 삽질을 했었습니다.

코드의 로직이 제대로 되었는지는 확인해보진 않았으나 파이썬에서는 돌아갔다고 하니 문제는 없을테고.. long long을 __int128로 바꿨을 때 무한 루프는 안 돈다는 점에서 일단 오버플로우가 문제가 아닐까 싶네요.

+추가로 확인해보니 입력 제한보다도 훨씬 작은 숫자에서도 돌지 않습니다.

찾은 제일 작은 케이스가 4294967311인데 소수임에도 __isprime에서 false를 반환합니다.

kimhs 2년 전 0

반례 감사합니다!

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

문제

문제

출처

ICPC

파이썬으로는 맞았는데 c++로 푸니까 시간초과가 납니다.

kimhs 2년 전 0

ldhun041203 2년 전 1

kimhs 2년 전 0

yup0927 2년 전 1

kimhs 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말