POJ百练 - 1183:反正切函数的应用

链接：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;
}