알렉산드리아의 디오판토스(7516, G1, c++)

알렉산드리아의 디오판토스

알렉산드리아의 디오판토스

문제

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며,
n이 주어진다. (1 ≤ n ≤ 109)

출력

각각의 테스트 케이스마다 “Scenario #i:”를 출력하고, 주어진 n에 대한 방정식의 해의 개수를 출력한다.
각 테스트 케이스 사이에는 빈 줄을 출력한다.

풀이

1/x + 1/y = 1/n를 식으로 풀어보면 (x+y)/xy = 1/n, xy/(x+y) = n이다.
한번 더 정리하면 xy = n(x+y), x = ny/(y-n) 가 된다.

이 때 x는 양수이므로 y>n이고 그러면 y=n+k로 놓을 수 있다.
y=n+k를 대입하면 x = (n^2+kn)/k = n^2/k + n 이고, 이는 정수여야 한다.

x<=y이므로 n^2/k <= k 여야하고 이것은 n<=k라는 의미이다.
즉 k는 n^2의 약수이며 n<=k인 수이므로 n을 소인수 분해한 다음 약수 개수를 구하는 공식을 통해서
n^2의 약수의 개수를 구할 수 있고, 약수 중 n보다 큰 수는 총 약수 개수/2+1을 한 수이다.

#define ll long long
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;
int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long mod = 1e9+7;
        
    bool flag=0; 
    long long a, b, c, d;
    long long n, m, t, k=0;
    long long ans = 1e18;

    cin >> t;
    while(t-->0){
        k++;
        cin >> n;
        map<long long, long long> mp;

        //n을 소인수분해 한 다음에 제곱한걸 계산해서 나누기2 + 1

        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                if(mp.find(i)!=mp.end()){
                    mp[i]++;
                }
                else{
                    mp.insert({i, 1});
                }
                n/=i;
                i=1;
            }
        }
        if(n>=2){
            if(mp.find(n)!=mp.end()){
                    mp[n]++;
                }
            else{
                mp.insert({n, 1});
            }
        }
        ans=1;
        for(auto a:mp){
            //cout << a.first << ' ' << a.second << '\n';
            ans*=(a.second*2+1);
        }
        cout << "Scenario #" << k << ":\n";
        cout << ans/2+1 << "\n\n";
    }

    return 0;
}