Problem 108 : Diophantine reciprocals I (30%)

Description

original

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

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

For n = 4 there are exactly three distinct solutions:

\[\frac{1}{5} + \frac{1}{20} = \frac{1}{4}\] \[\frac{1}{6} + \frac{1}{12} = \frac{1}{4}\] \[\frac{1}{8} + \frac{1}{8} = \frac{1}{4}\]

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

간략해석

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

Idea & Algorithm

naive idea

다음 식을 만족하는 지는 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$의 식을 인수분해해보면 알 수 있다.

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

여기서 $x \equiv y$일때가 $x$의 최댓값이고 이때의 $x$값은 $2n$이다. 또한 이때 $x$가 $n$보다 같거나 작다면 항상 식이 성립하지 않으므로

즉 위식을 만족하기 위해서는 $n \le x \le 2n $임을 알 수 있다.

그렇다면 $n$에 따른 해의 최대 개수는 $x$의 범위에 따라 $n+1$부터 $2n$까지니 총 $n$개다. 즉 반복문을 1000부터 하여 위 조건을 만족하는 해를 계속 찾을 수 있다.

하지만 이렇게 최적화했다고 생각했지만 이런 식으로 하면 만약 정해가 100000이상만 되도 연산이 100억번정도 연산을 해야하므로 TLE가 난다. ($\because O(n^2)$)

advancde idea에서 조금 더 생각해보자.

advanced idea

우선 $x$와 $y$의 최솟값을 알았으니 식을 다시 전개해보자.

\[\frac{1}{x} + \frac{1}{y} = \frac{1}{n+x'} + \frac{1}{n+y'} = \frac{2n + x' + y'}{n^2+nx' + ny' + x'y'} = \frac{1}{n}\] \[\to n\cdot (2n + x' + y') = n^2+nx' + ny' + x'y'\] \[\to n^2 = x'y'\]

$x$와 $y$를 다음과 같이 정의했을 때, 다음과 같이 $n^2$의 인수분해 문제로 변환할 수 있다.

그렇다면 $n^2$은 제곱수이므로 $x’\le y’$를 만족하는 쌍의 개수는 $\frac{\tau(n^2)+1}{2}$개임을 알 수 있다. 그렇다면 약수의 개수는 에라토스테네스의 체 변형으로 $O(nlogn)$으로 전처리할 수 있으니 쉽게 풀 수 있다.

source code

정답이 언제나올지 몰라서 전처리를 $10^7$까지 구해줬다.

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

const int SZ = 1e7;

int arr[SZ];

void era(){
  for(int i = 1 ; i < SZ ; i++) arr[i] = 1;
  for(int i = 2 ; i < SZ ; i++){
    if(arr[i]!=1) continue;
    for(int j = i ; j < SZ ; j += i){
      int cnt = 0, tmp = j;
      while(tmp % i == 0){
        cnt++;
        tmp /= i;
      }
      arr[j] *= cnt*2+1;
    }
  }
}

int main(){
  era();
  for(int i = 1000 ; ; i++){
    if((arr[i]+1)/2>1000){
      cout << i << endl;
      return 0;
    }
  }
}

Problem 108