【小码匠自习室】ABC144-C：一个字：爽；两个字：好爽；三个字：特别爽

2022-06-16 18:18:48 浏览数 (2)

碎碎念

  • 一个字：爽；两个字：好爽；三个字：特别爽。这是迄今为止做的最爽的一道题。
    • 老码农：爽你个大头鬼，老做爽题，你的水平就会停滞不前

ABC144-C-01

标签

  • 数学、约数分解

题目地址

  • C - Walk on Multiplication Table
    • https://atcoder.jp/contests/abc144/tasks/abc144_c

题目描述

Problem Statement

Takahashi is standing on a multiplication table with infinitely many rows and columns.

The square (i,j) contains the integer i

times

j. Initially, Takahashi is standing at (1,1).

In one move, he can move from (i,j) to either (i 1,j) or (i,j 1).

Given an integer N, find the minimum number of moves needed to reach a square that contains N.

Constraints

  • 2 leq N leq 10^{12}
  • N is an integer.

Input

Input is given from Standard Input in the following format:

代码语言：javascript复制
N

Output

Print the minimum number of moves needed to reach a square that contains the integer N.

Sample Input 1

代码语言：javascript复制
10

Sample Output 1

代码语言：javascript复制
5

(2,5) can be reached in five moves. We cannot reach a square that contains 10 in less than five moves.

Sample Input 2

代码语言：javascript复制
50

Sample Output 2

代码语言：javascript复制
13

(5, 10) can be reached in 13 moves.

Sample Input 3

代码语言：javascript复制
10000000019

Sample Output 3

代码语言：javascript复制
10000000018

Both input and output may be enormous.

题解

小码匠题解

代码语言：javascript复制
void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long n;
    cin >> n;
    for(long long i = sqrt(n); i > 0; --i) {
        if(n % i == 0) {
            cout << i - 1   (n / i) - 1;
            return;
        }
    }
}

参考题解

代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    long long res = N   1 - 2; // (a, b) = (1, N)
    for (long long a = 1; a * a <= N;   a) {
        if (N % a == 0) res = min(res, a   N/a - 2);
    }
    cout << res << endl;
}
contains input integer output sample

0 人点赞