Codeforces Round 828 (Div. 3) - E2. EDivisible Numbers (hard version) (1900)

E2. EDivisible Numbers (hard version)

$a < x \le c, ~ b < y \le d$ 여야 하고, $ab \mid xy$ 여야 한다.

$x$ 를 고정시키고 생각해보자.

$xy \equiv 0 \pmod {ab}$ 이므로 $y \equiv 0 \pmod {\dfrac{ab}{gcd(x,ab)}}$ 이다.

따라서 $y$는 $\dfrac{ab}{gcd(x,ab)}$ 로 나누어 떨어져야 하고, 이를 $X$라 할 때

$y=\left\lfloor \dfrac{d}{X} \right\rfloor \cdot X \ge b$ 인지 확인하면 이 $y$가 범위내에 있다고 알 수 있다.

$x$는 $a < x \le c$의 모든 수를 검사하면 너무 느리므로 $X$값의 후보를 본다.

결국 $X$값의 후보는 $ab$의 약수이기 때문에 $ab$의 모든 약수를 찾아서 검사하면 된다.

그런데 $ab \le 10^{18}$ 이므로 이 방법또한 폴라드로를 쓰지 않으면 모든 약수를 찾기가 어렵다.

나는 무지성으로 폴라드로를 써서풀었다.

$a,b \le 10^9$ 임을 이용해서 일단 $a$와 $b$를 모두 소인수분해 해보자.

그러면 $ab$의 약수로 가능한 것은 그 소인수분해 된 것들로 모두 만들어볼 수 있고 대략 약수가 $1400$개로 국한된다.

이렇게 만들어진 모든 $X$들에 대해서 모두 검사해보면 된다.

소인수분해는 $O(\sqrt{ n })$이 걸리므로 $O(T \cdot (\sqrt{ 10^9 }+(1400)^2))$ 정도로 문제를 해결할 수 있다.

void solve() {  
   int a, b, c, d;  
   cin >> a >> b >> c >> d;  
  
   auto f = pollard.factorize(a * b);  
   debug(a * b);  
   vi div;  
   function<void(int, int)> fn = [&](int i, int d) -> void {  
      if (i == sz(f)) {  
         div.pb(d);  
         return;  
      }  
  
      for (int j = 0, k = 1; j <= f[i].se; j++, k *= f[i].fi) {  
         fn(i + 1, d * k);  
      }  
   };  
   fn(0, 1);  
  
   for (int d1: div) {  
      int q1 = (a + 1 + d1 - 1) / d1;  
      int q2 = c / d1;  
      if (q1 <= q2) {  
         int d2 = a * b / d1;  
         int q3 = (b + 1 + d2 - 1) / d2;  
         int q4 = d / d2;  
         if (q3 <= q4) {  
            cout << q1 * d1 << ' ' << q3 * d2 << endl;  
            return;  
         }  
      }  
   }  
   cout << -1 << ' ' << -1 << endl;  
}