[数据结构与算法]B - ，

B - ，

Problem Statement

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

The square?(i,j)(i,j)?contains the integer?i \times ji×j. Initially, Takahashi is standing at?(1,1)(1,1).

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

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

Constraints

• 2 \leq N \leq 10^{12}2≤N≤1012
• NN?is an integer.

Input

Input is given from Standard Input in the following format:

NN

Output

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

Sample 1

Inputcopy	Outputcopy
10	5

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

Sample 2

Inputcopy	Outputcopy
50	13

(5, 10)(5,10)?can be reached in?1313?moves.

Sample 3

Inputcopy	Outputcopy
10000000019	10000000018

Both input and output may be enormous.

?关于找一个数number最相近的两个因子步骤：

1，看number是否是完全平方数

2，如果不是，设开方后取整的数为k，先比较k^2和(k+1)^2哪个和number更相近，再从相近的那个数往前找较小的相近因子

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
using namespace std;
typedef long long ll;
bool isown(ll k) {//判断质数
	if (k == 1) return true;
	if (k == 2) return false;
	ll a = sqrt(k);
	for (ll i = 2; i <= a; i++) {
		if (k % i == 0) return false;
	}
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll t;
	ll number;
	cin >> number;
	if (isown(number) == true) //是质数的话，向下走number-1步到达（1，number）
		cout << number - 1;
	else {//不是的话，求最相近的两个因子，这样这两个数的和最小（差值小的两个数相乘，对乘积贡献多）
		ll a = sqrt(number);
		if (number % a == 0) {//如果是完全平方数的话
			ll b = number / a;
			cout << a + b - 2;
		}
		else {
			ll lowa = a * a, lowb = (a + 1) * (a + 1);//寻找较小的那个因子
			ll low = abs(number - lowa) < abs(number - lowb) ? a : a + 1;
			ll bit;
			for (ll i = low - 1; i >= 1; i--) {
				if (number % i == 0) {
					bit = i;
					break;
				}
			}
			ll sit = number / bit;
			cout << sit + bit - 2;
		}
	}
	return 0;
}

?