CF#554 C Neko Does Maths

分类:题解, 发布于:2019-04-25 00:40:00, 更新于:2019-04-25 01:50:02 CC-BY-NC-SAv4 评论

题意

已知$a$$b$,求$k$,使$a+k$$b+k$的最小公倍数最小。

思路

嗯,这么弱智的题目都不会做!

  • 如果$b - a > a$$a + k$是最小的$b - a$的因数;
  • 否则$a + k$是第一个比$a$大的$b - a$的倍数。

然后……

被卡死了呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜

代码

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

ll A, B;

ll solve(ll a, ll b) {
  if (a == 1 || a == b || a == b - 1) return 0;
  ll d = b - a;
  if (d > a) {
    ll ans = d - a;
    ll m = (ll) sqrt(d) + 1;
    for (int i = 1; i < m; ++i) {
      if (d % i == 0) {
        if (i >= a) ans = min(ans, i - a);
        if (d / i >= a) ans = min(ans, d / i - a);
      }
    }
    return ans;
  } else {
    return ((a - 1) / d + 1) * d - a;
  }
}

int main() {
  cin >> A >> B;
  if (A > B) swap(A, B);
  cout << solve(A, B) << endl;
}

暴力求因数都能写错呜呜呜呜呜呜呜呜,回家种田去了

评论