[알고스팟 PASS486] 비밀번호 486

성공코드는 제일 아래 코드!

시간 초과 에러가 많이 나왔던 문제.

 

처음에는 한 숫자에 대해서 하나하나 다 나눠가면서 풀어봄.

당연히 시간 초과 ^^

 

// O(sqrt(n)) --> 시간초과
// sqrt(n)까지 하나하나 다 나눠보는 방식
int solve1(int n, int lo, int hi){
    int i, cur;
    int possible = 0;
    for(cur = lo; cur <= hi; cur++){
        int count = 2; // 1, cur
        for(i = 2; i < sqrt(cur); i++){
            if(cur % i == 0)
                count += 2;
        }
        if(i == sqrt(cur))
            count += 1;
        
        if(count == n)
            possible++;
    }
    return possible;
}
 
 

---

그래서 포기하고 다시 에라토스테네스의 체를 이용해서 소수 판단 후 소인수분해를 진행.

그다음 소인수 분해한 식으로 공약수 수를 구하는 공식을 사용해서  구하기를 시도함.

 

 

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
#define MAX_NUM 10000000
int primeFactor[MAX_NUM+1];
vector<int> primes;
 
void eratos(){
    for(int i = 1; i <= MAX_NUM; i++)
        primeFactor[i] = i;
    int maxi = (int)sqrt(MAX_NUM);
    for(int i = 2; i <= maxi; i++){
        if(primeFactor[i] == i){
          //  primes.push_back(i);
            for(int j = i*i; j <=MAX_NUM; j += i){
                primeFactor[j] = i;
            }
        }
    }
}
// 시간초과...ㅡㅡ
bool hasNFactors(int n, int cur){
    map<int, int> curFactors;
    int count = 1;
    
    if(primeFactor[cur] == cur){
        count = 2;
        if(count != n)
            return false;
        return true;
    }
    while(cur > 1){
        curFactors[primeFactor[cur]]++;
        cur /= primeFactor[cur];
    }
    for(map<int, int>::iterator it = curFactors.begin(); it != curFactors.end(); it++){
        count *= (it->second+1);
    }
    
    if(count == n)
        return true;
    return false;
}
// 시간초과...ㅡㅡ
// 소인수분해 후 지수들을 이용하여 약수의 개수를 구하는 방식
int solve2(int n, int lo, int hi){
    int count = 0;
    for(int i = lo; i <= hi; i++)
        if(hasNFactors(n, i)) count++;
    return count;
}
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    int n, lo, hi;
    eratos();
    while(t--){
        cin >> n >> lo >> hi;
        cout << solve3(n, lo, hi) << endl;
    }
    return 0;
}
 
 
 

시간 초과 실패. ^^ ㅎ.... 

살짝 포기하고 싶어 졌다.

---

마지막으로  모든 숫자에 대해서 미리 약수 개수를 다 구하는 방식을 이용했다.

약간 버겁긴하지만 시간 복잡도는 O(nlgn)으로 수렴한다고 한다.

 

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
#define MAX_NUM 10000000
int factorsCount[MAX_NUM+1];
 
 
// 모든 수의 약수 구하기
void calcEveryNum(){
    for(int i = 1; i <= MAX_NUM; i++){
        for(int j = i; j <= MAX_NUM; j += i){
            factorsCount[j]++;
        }
    }
}
 
int solve3(int n, int lo, int hi){
    int count = 0;
    for(int i = lo; i <= hi; i++){
        if(factorsCount[i] == n)
            count++;
    }
    return count;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    int n, lo, hi;
    calcEveryNum();
    while(t--){
        cin >> n >> lo >> hi;
        cout << solve3(n, lo, hi) << endl;
    }
    return 0;
}
 
 
 

성공!!! :)