[C++] 백준 27725번: 지수를 더하자 - Math

https://www.acmicpc.net/problem/27725

27725번: 지수를 더하자

 

문제가 너무 어렵게 생겨서 지레 겁을 먹었던 문제

그런데 읽다보니 그냥 소인수분해를 이용한 문제 풀이라는 것을 알고

나름 간단하게 해결했다.

다만 문제 조건 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으로 진행해주면 된다.

 

#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;
}