🚀 [PASS486] 문제 😊😊😊😊😊
재훈이는 한 번 담배를 끊겠다고 다짐할 때마다 이메일 계정 비밀번호를 바꾸는 습관이 있습니다. 재훈이는 비밀번호를 항상 “no-smokX” 와 같이 정하는데, 여기서 X는 1자리 이상의 자연수입니다. 재훈이에게는 k번째로 금연을 다짐할 때는 항상 정확히 k개의 약수를 갖는 숫자로 X를 선택하는 습관이 있습니다. 예를 들어 재훈이가 12번째로 금연을 다짐했을 때 쓴 비밀번호는 no-smok486 이었습니다. 486 에는 1, 2, 3, 6, 9, .., 243, 486으로 모두 12개의 약수가 있으니까요.
재훈이는 금연을 다짐하고 비밀번호를 바꾼 뒤 잠들었는데, 아침에 일어나서는 비밀번호가 기억나지 않는다는 사실을 깨달았습니다. 재훈이가 어렴풋이 기억하는 것은 비밀번호가 n개의 약수를 가진다는 사실과, 비밀번호가 아마도 [lo,hi] 범위 내에 있을 거라는 것 뿐입니다 (범위는 양 끝의 수를 포함합니다).
재훈이가 예상한 범위 내에 비밀번호가 될 수 있는 수가 몇 개나 되는지 계산하는 프로그램을 작성하세요.
🔑 [풀이]
각 숫자의 가장 작은 소인수와, 소인수 분해에서 이 숫자가 몇 몇 번이나 나타나는 지를 저장하는 코드를 getMinfactor() 에서 구현한뒤,
n의 가장 작은 소인수가 p이고, 이 소인수가 a번 출현한다면 factor(n/p)X(a+1)/a 로 factor(n) 을 계산합니다.
다음을 참고하면 빠르게 해결할 수 있습니다. 에라토스테네스의 체를 이용
- \(sqrt(n)\) 까지만 검색합니다. (합성수 n 이 pXq로 포현된다면 한 수는 한상 \(sqrt(n)\) 이하, 나머지 한 수는 \(sqrt(n)\) 이상이기 때문)
- i의 배수들을 지울 때 2xi 에서 시작하는 것이 아니라 ixi 부터 시작합니다. (이미 2*i의 배수들은 이전 2의 배수를 지울때 지워졌기 때문)
⌨️ 입력
입력의 첫 줄에는 테스트 케이스의 수 c(c <= 50)가 주어집니다. 그 후 c줄에 각 3개의 정수로 n (n < 400), lo , hi(1 <= lo <= hi <= 10,000,000)이 주어집니다. hi-lo 는 항상 1백만 이하입니다.
🖥 출력
각 테스트 케이스마다, 해당 범위 내에 비밀번호가 될 수 있는 숫자가 몇 개인지 출력합니다.
🖱 입력 예제
3
2 2 10
12 486 486
200 1000000 2000000
💻 출력 예제
4
1
19
💎 전체 코드는 다음과 같습니다.
//
// PASS486.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/12.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
ifstream fin("PASS486.txt");
// brute force 로 문제해결
void brute_force();
const int MAX = 10000000;
int n, lo, hi;
int minFactor[MAX+1];
int minFactorPower[MAX+1];
int factors[MAX+1];
// 소인수 분해를 통해 약수의 개수를 구하는 공식을 이용하자
// ex) 100 = 2^2 + 5^2 -> (위의 지수들+1) 를 모두 곱해준다 -> 3 *. 3 = 9개
void getMinfactor(){
minFactor[0] = -1;
minFactor[1] = -1;
for(int i=2; i<MAX+1; i++){
minFactor[i] = i;
}
// root(MAX) 만큼 순회한다.
for(int i=2; i<=int(sqrt(MAX)); i++){
if(minFactor[i] == i)
// i^2 부터 순회한다.
for(int j=i*i; j<=MAX; j+=i)
if(minFactor[j]==j) minFactor[j] = i;
}
}
void solve(){
factors[1] = 1;
for(int i=2; i<=MAX;i++){
// 소수이면
if(minFactor[i] == i){
factors[i] = 2;
minFactorPower[i] = 1;
}
else{
int min_prime = minFactor[i];
int divisor = i / min_prime;
// 더이상 min_prime 으로 나누어 떨어지지 않을때
if(min_prime != minFactor[divisor]){
minFactorPower[i] = 1;
}
// 더 나누어 질 경우
else{
minFactorPower[i] = minFactorPower[divisor] + 1;
}
int exponentNum = minFactorPower[i];
factors[i] = (factors[divisor] / exponentNum) * (exponentNum + 1);
}
}
}
int main(){
int test_case;
fin >> test_case;
getMinfactor();
solve();
//brute_force();
for(int test=0; test < test_case; test++){
//int n, lo, hi;
fin >> n >> lo >> hi;
// solve(); 시간초과
int count= 0;
for(int i=lo; i<hi+1; i++){
if(factors[i] == n)
count++;
}
cout << count << endl;
}
}
// 부르트 포스!
void brute_force(){
memset(factors,0,sizeof(factors));
for(int i=1; i < MAX+1 ; i++){
for(int j=i; j < MAX+1;j+=i)
factors[j]++;
}
}
Comments