Problem 110 : Diophantine reciprocals II (40%)

Description

original

In the following equation x, y, and n are positive integers.

\[\frac{1}{x} + \frac{1}{y} = \frac{1}{n}\]

It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.

What is the least value of n for which the number of distinct solutions exceeds four million?

간략해석

$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$을 만족하는 $x \le y$인 쌍이 4,000,000개보다 많은 $n$을 구하시오.

Idea & Algorithm

naive idea

이 문제의 naive한 아이디어는 108번 문제에 설명되어 있다.

추가적으로 설명하자면 $\frac{\tau(n^2)+1}{2}$가 4,000,000개보다 많기 위해서는 수가 4,000,000보다 커야하는데 대략 추측하건데 수 자체는 int범위를 매우 넘는다.

advanced idea

우선 문제에서 요구하는 약수의 개수를 구하는 식은 다음과 같다.

\[n = {p_1}^{e_1}\cdot{p_2}^{e_2}...{p_k}^{e_k} \to \tau(n^2) = \prod_{i=1}^k {2e_{i}+1}\]

임을 알 수 있다. 그렇다면 수의 범위를 대략 알기위해 $\frac{\tau(n^2)+1}{2}$가 4,000,000개인 수를 하나 찾아보면 다음과 같이 생각해볼 수 있다.

$log_3 8000000 = 14.46…$이므로 소수 15개의 곱으로 이루어진 $n$은 약수 개수가 조건이 만족하고 그 수는 614,889,782,588,491,410로 겨우 long long범위 안이다.

또한 $n$을 구할때, 소수는 반드시 앞에서 차근차근 곱해도 된다. 그 이유는 약수의 개수는 수의 소수의 개수의 곱으로 이루어지기에 소수는 앞에서부터 구해주는 것이 좋다.

또한 나머지 부분이 같을 경우 $x < y$에 대하여 ${p_i}^{x}\cdot{p_j}^{y} < {p_i}^{y}\cdot{p_j}^{x}$ 다음과 같은 식을 만족하기에 $p_i < p_j$이면 $e_i \ge e_j$임을 알 수 있다.

그렇다면 임의의 값에서 소수는 최대 15개가 필요하다는 것을 알았고, 지수가 감소수열임을 알았으니 나머지는 재귀로 그 값을 구할 수 있다.

source code

c++로 할때는 overflow가 나지 않게 잘 설정해주자. 소수 15개는 수가 적기때문에 배열에 미리 넣어도 괜찮다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int SZ = 15;
const int MX = 4e6;

vector<ll> p;
int arr[100];

void era(){
  int cnt = SZ;
  for(int i = 2 ; cnt ; i++ ){
    if(arr[i]) continue;
    p.push_back(i);
    cnt--;
    for(int j = i*i; j < 100 ; j+=i){
      arr[j] = 1;
    }
  }
}

ll ans = 1;

void dfs(int idx, ll val, int cnt, int last){
  if( (cnt+1)/2 > MX){
    ans = min(ans, val);
    return ;
  }
  ll pri = p[idx];
  for(int i = 0 ; val < ans / pri && i <= last ; i++){
    dfs(idx+1, val * pri, cnt*(2*(i+1)+1), i);
    pri *= p[idx];
  }
}

int main(){
  era();
  ll cnt = 1;
  for(int i = 0 ; i < SZ ; i++ ) ans *= p[i];
  dfs(0, 1, 1, 40);
  cout << ans;
}

Problem 110