합과 곱

아… 솔직히 이거 접근이 잘 안돼서 좀 힘들었습니다.. 사실 이거 산술기하까지는 갔는데 그걸 이렇게 발전시키는 아이디어를 바로 생각을 해내질 못해서 많이 묶여있었네요…

사실 문제는 그렇게 어려운편은 아니지만 좀 흥미롭게 풀 수 있었던 것 같아요.

저의 아이디어는 이제 “리스트에는 정수가 아닌 수가 포함될 수도 있다.”이러한 문장이 문제에 존재했기 때문에 S/n으로 균일하게 나눈 후에.. 이거를 곱했을 때.. P보다 크거나 같은 수를 찾으면 되겠구나 생각했습니다.

이때 여기까지 오면서 산술기하를 사용한 것이구요.

산술기하

$$\text{산술기하 평균 부등식(AM-GM Inequality)}$$

두 양수 $a$와 $b$에 대해, 산술평균은 기하평균보다 크거나 같다는 것을 증명해보겠습니다

$$\frac{a+b}{2}\ge \sqrt{ab}$$

그리고 등호는 $a=b$일 때만 성립합니다

$$\text{보통 수학시간에 배우는 기본적인 산술기하 평균 부등식}$$

$(a-b{)}^2\ge 0$이라는 사실에서 시작합니다. 이것은 모든 실수의 제곱이 음이 아니기 때문입니다

$$\begin{array}{rl}(a-b{)}^2& \ge 0\\ a^2-2ab+b^2& \ge 0\\ a^2+2ab+b^2& \ge 4ab\\ (a+b{)}^2& \ge 4ab\\ a+b& \ge 2\sqrt{ab}\\ \frac{a+b}{2}& \ge \sqrt{ab}\end{array}$$

등호는 $a-b=0$, 즉 $a=b$일 때만 성립합니다

$$\text{우리가 알아야될 일반화된 산술기하평균 부등식}$$

$n$개의 양수 $a_1,a_2,\dots ,a_n$에 대해서도 산술평균과 기하평균의 부등식이 성립!

$$\frac{a_1+a_2+\cdots +a_n}{n}\ge \sqrt[n]{a_1\cdot a_2\cdot \dots \cdot a_n}$$
$$\text{귀납법을 이용한 증명}$$

$n=2$인 경우는 이미 증명했습니다. $n=2^k$인 경우에 대해 귀납법을 사용할 수 있습니다

$n=2^k$일 때 부등식이 성립한다고 가정합시다. $2^{k+1}$개의 수 $a_1,a_2,\dots ,a_{2^{k+1}}$에 대해

$$\begin{array}{rl}\frac{a_1+\cdots +a_{2^{k+1}}}{2^{k+1}}& =\frac{1}{2}\left(\frac{a_1+\cdots +a_{2^k}}{2^k}+\frac{a_{2^k+1}+\cdots +a_{2^{k+1}}}{2^k}\right)\\ & \ge \frac{1}{2}\left(\sqrt[2^k]{a_1\cdots a_{2^k}}+\sqrt[2^k]{a_{2^k+1}\cdots a_{2^{k+1}}}\right)\\ & \ge \sqrt{\sqrt[2^k]{a_1\cdots a_{2^k}}\cdot \sqrt[2^k]{a_{2^k+1}\cdots a_{2^{k+1}}}}\\ & =\sqrt[2^{k+1}]{a_1\cdots a_{2^{k+1}}}\end{array}$$

여기서도 등호는 모든 $a_i$가 서로 같을 때만 성립합니다.

그래서 이렇게 산술기하평균 부등식을 통해서 문제를 풀 수 있구요..

식을 구했다! 그르면 이제 어떻게 적용할 것이냐?

각 원소가 있죠? (S/n) >= sqrt(P, n) -> (S/n)^n >= P 이렇게해서 n을 쭉 순회하면서 구하면 됩니다.

그리고 1 1, 3 3과 같이 S와 P가 같은 경우는 1로 고정 출력하고 이후에는 그냥 2부터 S까지 쭉 순회하면 된답니다!

#include <iostream>
#include <queue>
#include <algorithm>
#include<set>
#include <map>
using namespace std;
using ll = long long;

int inf = 1e9;

double s, p;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s >> p;
    
    
    if(s == p){
        cout << 1;
        return 0;
    }
    for(double n = 2; n <= s; n++){
        double element = s/n;
        
        double current = 1;
        double idx = 0;
        while(idx++<n) current*=element;
        
        if(current < p) continue;
        
        
        
        cout << n;
        return 0;
    }
    cout << -1;
    
    return 0;
}