백준 15701번 순서쌍

문제 링크입니다: https://www.acmicpc.net/problem/15701

처음 시도는 배열을 이용해서 소인수분해를 한 후 (지수+1)끼리 곱해서 약수의 갯수를 구하려고 했으나 배열을 1,000,000,000 크기로 지정할 수 없기 때문에 실패했습니다.

이후에는 벡터를 이용해서 이중 for문을 돌려 algorithm 헤더에 있는 count 함수를 사용해서 찾아보려고 했지만 메모리 초과가 떴고 메모리 초과가 안 떴다고 하더라도 TLE가 떴을 것입니다.

따라서 http://jaimemin.tistory.com/445의 에라토스테네스의 체에서 처럼 제곱근까지 약수의 갯수를 구한 다음에 두배를 시켜 구했습니다. 약수의 순서쌍은 대칭이기 때문에 위와 같은 방법으로 풀 수 있었습니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N; //주어진 숫자

 

int divisor(void)

{

        int cnt = 0;

        bool square = false; //제곱수인가?

 

        //에라토스테네스의 체에서 확인했다싶이 i*i<=N까지 찾아보면 된다

        //약수의 순서쌍은 대칭이기 때문에

        for (int i = 1; i*i <= N; i++)

        {

                 if (!(N%i))

                         cnt++;

                 if (i*i == N)

                         square = true;

        }

        if (!square)

                 cnt *= 2;

        else

                 cnt = cnt * 2 - 1;

        return cnt;

}

 

int main(void)

{

        cin >> N;

       

        cout << divisor() << endl;

        return 0;

}

아래는 TLE가 떴을법한 코드입니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000000 + 1;

 

vector<int> countDivisor;

 

int N; //주어진 숫자

 

void divisor(void)

{

        for (int i = 1; i <= N; i++)

                 for (int j = 1; j <= N / i; j++)

                         countDivisor.push_back(i*j);

}

 

int main(void)

{

        cin >> N;

 

        divisor();

        //vector 내의 N 갯수를 구하면 약수의 갯수

        cout << std::count(countDivisor.begin(), countDivisor.end(), N) << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~