鏈接：
http://poj.grids.cn/practice/1183/
方法1:
本題很容易推斷出,a = (b*c-1)/(b+c), 由于需要求(b+c)的最小值,根據高中的函數思想,如果(b+c)能夠轉換為關于b或者c的函數就好辦了,剛好這里已經有個b和c的關系式子了,可以推導出(b+c) = (c^2+1)/(c-a),這個時候只需要求f(c)的最小值,但是c必須取整數,對這個函數可以求導,也可以進行變形,變形后可以得到f(c) = (c-a)
+ 2*a + (a^2+1)/(c-a),令x=c-a,那么可以得到(b+c)=f(x)=x+2*a+(a^2+1)/x, 其中x必須是整數,到現在為止就是一個用程序模擬高中時候學過的雙曲線函數的求最值問題了,我們知道該函數的極值點是sqrt(a^2+1),但是由于x必須是整數,我們必須從極值開始往下和往上找到一個最小值,然后取2者中的最小值...
這樣這個題就解出來了...
代碼:
#include <stdio.h>
#include <iostream>
#include <math.h>
//b + c = (c^2 + 1) / (c - a) = (c-a) + (2 * a) + (a^2 + 1) / (c -a)
//令c-a = t, f(t) = t + 2*a + (a^2+1)/ t
//因為f(t)在sqrt(a^2+1)時取最小值,但是由于t只能取整數,
//所以,必須從極值點往下和往上尋找最小的值,然后取2者中最小的
int main()
{
long long a;
while (std::cin >> a)
{
long long nTemp = a * a + 1;
long long nDown = sqrt(nTemp);
long long nUp = nDown;
long long one, two;
while (nTemp % nDown )
{
nDown--;
}
one = 2 * a + nTemp / nDown + nDown;
while (nTemp % nUp )
{
nUp++;
}
two = 2 * a + nTemp / nUp + nUp;
std::cout << (one < two ? one : two) << std::endl;
}
return 0;
}
方法2:
#include <stdio.h>
#include <iostream>
#include <math.h>
//a = (b*c-1)/(b+c)
//令b = a + m, c = a + n, c >= b
//-> a*(2*a+m+n) = (a+m)*(a+n)-1
//m*n = a^2 + 1 (n>=m)
//所以,求出a^2+1所有因子對,取其中m+n最小的即可
int main()
{
long long a;
while (std::cin >> a)
{
long long m, n;
long long nTemp = a * a + 1;
long long nMax = sqrt(nTemp);
long long nRes = 1 + nTemp;
for (m = 2; m <= nMax; ++m)
{
if (nTemp % m == 0)
{
n = nTemp / m;
if (m + n < nRes)
{
nRes = m + n;
}
}
}
std::cout << 2 * a + nRes << std::endl;
}
return 0;
}