PS/BOJ
[C++] 백준 27725번: 지수를 더하자 - Math
__PS
2023. 3. 12. 14:39
728x90
https://www.acmicpc.net/problem/27725
27725번: 지수를 더하자
서로 다른 $N$개의 소수로 이루어진 집합 $P=\{p_{1}, p_{2}, \cdots, p_{N}\}$이 있다. 양의 정수 $i$에 대하여 $\frac{i}{p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times \cdots \times p_{N}^{a_{N}}}$의 값이 양의 정수가 되도록 하는
www.acmicpc.net
문제가 너무 어렵게 생겨서 지레 겁을 먹었던 문제
그런데 읽다보니 그냥 소인수분해를 이용한 문제 풀이라는 것을 알고
나름 간단하게 해결했다.
다만 문제 조건 K <= 10^12였기에 모든 수를 하나하나 소인수분해를 할 수는 없었다.
그래서 생각했던 것이 무지성 나누기
N이하의 수를 소수 p로 나눈다면 N / p의 값이 p가 들어있는 개수일 것이다.
조금 더 쉽게 풀어쓰자면
N = 100, p = 2라면
1 ~ 100 사이에 2로 나누어 떨어지는 수는 50개일 것이고,
1 ~ 100 사이에 4로 나누어 떨어지는 수는 25개일 것이다.
이는 2로 나눈 수를 다시 한번 2로 나누는 것과 같다고 해석할 수 있다.
1 ~ 100 사이에 8로 나누어 떨어지는 수는 12개인데,
이 역시 이는 4로 나눈 수를 다시 한번 2로 나누는 것과 같다고 해석할 수 있다.
즉, 1 ~ 100 사이의 수를 모두 소인수분해 하려면
단순히 N / p 를 해주면 된다.
여기서 p는 p^n으로 진행해주면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <iostream>
#include <vector>
using namespace std;
using ll=long long;
vector<int>v;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, x; cin >> n;
ll k, y, ans=0;
for(int i=0; i<n; i++){
cin >> x;
v.push_back(x);
}
cin >> k;
for(int i=0; i<v.size(); i++){
x=v[i], y=x;
if(x>k) break;
while(1){
if(y<=k){
ans+=(k/y);
y*=x;
}
else break;
}
}
cout << ans;
}
|
cs |