鏈接：
http://poj.grids.cn/practice/1183/
方法1:
本題很容易推斷出,a = (b*c-1)/(b+c), 由于需要求(b+c)的最小值,根據(jù)高中的函數(shù)思想,如果(b+c)能夠轉換為關于b或者c的函數(shù)就好辦了,剛好這里已經(jīng)有個b和c的關系式子了,可以推導出(b+c) = (c^2+1)/(c-a),這個時候只需要求f(c)的最小值,但是c必須取整數(shù),對這個函數(shù)可以求導,也可以進行變形,變形后可以得到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必須是整數(shù),到現(xiàn)在為止就是一個用程序模擬高中時候學過的雙曲線函數(shù)的求最值問題了,我們知道該函數(shù)的極值點是sqrt(a^2+1),但是由于x必須是整數(shù),我們必須從極值開始往下和往上找到一個最小值,然后取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只能取整數(shù),
//所以,必須從極值點往下和往上尋找最小的值,然后取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;
}