b893: 勘根定理

內容

高中數學的等級明顯比國中高出了許多，這點在小紫進入了板橋高中之後她就清楚地體會到了 ── 以往國中輕鬆考都可以 90 分以上甚至滿分的數學，居然會不及格！
　　但儘管小紫受到了莫大的打擊，她依然想努力地把數學顧好，再加上他們的數學老師誇下海口，讓這次數學段考排名是三位數的同學兩個兩個分組，可以在第二次段考的時候針對各組進步最多分的那一位同學來做整組相對應的學期總成績加分，這種種契機讓小紫燃起了鬥志，於是她找了班上一位數學很好的同學波路特石與她同組，想讓第二次段考能夠有 90 分。

這天，小紫正好與波路特石在討論數學。
　　「欸欸，這個『甚根定理』是什麼東西啊？」
　　小紫對波路特石提出了疑問。
　　「ㄜ……那個是『勘』根定理。」
　　波路特石無奈地回應。
　　「沒差啦，我問你這個是什麼意思！」
　　「……」波路特石儘管感到很頭痛，但還是繼續解釋了下去：「勘根定理的概念其實很簡單，就是在講『當一個連續的函數 f(x)滿足 f(a)×f(b)<0 的時候，必可以在 a 和 b 之間找到至少一個根滿足 f(x)=0』，順帶一提，a、b 是實數。」
　　「為什麼？」
　　針對小紫再次的提問，波路特石在紙上畫出了一個直角座標，並在 x 軸的上方和下方各點出了一個點。
　　「因為我已經給出了『函數是連續的』這個條件，也就是說這個函數必不會間斷……你應該知道當 y 是 x 的函數，一個 x 最多只能對應到一個 y 吧？」
　　「知道。」
　　「好，那你模擬看看，假設你今天要從下面這個點，走到上面這個點，並且你的路徑一定要是連續的，又不能繞出去這兩點之間，請問你有辦法不經過 x 軸就到達上面的點嗎？」
　　「當然不能啊！」小紫在反駁波路特石的剎那間忽然靈光一閃、恍然大悟：　　「我懂了！所以在上面這個點和下面這個點之間一定會經過 x 軸，也就是 f(x)=0 的解嘛！」
　　「沒錯，這樣你應該就懂了。」
　　「謝謝！」

小紫非常的興奮，她又理解了一個新的定理，但有關於勘根定理的題目實在是太少了，於是她想自己出給自己題目，不過她卻沒辦法確認答案的正確性，又不想再打擾最近忙著程式競賽還願意花時間教自己數學的波路特石。

請你撰寫一個程式，幫小紫判斷她出的「多項式函數」所有根的範圍分別介於哪兩個連續整數之間，好讓小紫可以驗證正確答案。

輸入

每筆輸入有以空格隔開的 6 個整數，分別為 a、b、c、d、e、f，代表 ax⁵+bx⁴+cx³+dx²+ex+f，來表示小紫出給自己的函數題目。

0 0 6 -25 -29 20

輸出

請輸出這個函數所有的根分別介於哪兩個「連續」整數之間，並由小排到大，每一個根的範圍佔一行，每一行裡的兩個數字以空格隔開，小的在左。
若有無限多組根請輸出「Too many… = =”」(不含引號)；
若函數無實根請輸出「N0THING! >\\\<」(不含引號)。
若根恰為整數，請重複輸出兩次此根，並以空格隔開。

-2 -1
0 1
5 5

解題思路

先建好 pow 表，之後要使用直接查表省時間。

再來用迴圈窮舉帶入公式符合條件時輸出即可。

注意 ax⁵ 有可能會超過 int 上限、當輸入皆為 0 時要出輸出 Too many… = =

完整程式碼

AC (2ms, 112KB)

#include <stdio.h>

int pow[81][6];

int main()
{
    for (int i = -40; i <= 40; i++)
    {
        pow[40 + i][1] = i;
        pow[40 + i][2] = i * i;
        pow[40 + i][3] = pow[40 + i][2] * i;
        pow[40 + i][4] = pow[40 + i][3] * i;
        pow[40 + i][5] = pow[40 + i][4] * i;
    }
    long long fa, fb, a;
    int b, c, d, e, f;
    char noAns;
    while (scanf(" %lld %d %d %d %d %d", &a, &b, &c, &d, &e, &f) == 6)
    {
        if (a || b || c || d || e || f)
        {
            noAns = 1;
            fa = a * pow[0][5] + b * pow[0][4] + c * pow[0][3] + d * pow[0][2] + e * pow[0][1] + f;
            for (int i = 1; i <= 80; i++)
            {
                fb = a * pow[i][5] + b * pow[i][4] + c * pow[i][3] + d * pow[i][2] + e * pow[i][1] + f;
                if (!fb)
                    printf("%d %d\n", pow[i][1], pow[i][1]), noAns = 0;
                else if ((fa ^ fb) < 0 && fa)
                    printf("%d %d\n", pow[i - 1][1], pow[i][1]), noAns = 0;
                fa = fb;
            }
            if (noAns)
                puts("N0THING! >\\\\\\<");
        }
        else
        {
            puts("Too many... = =\"");
        }
    }
    return 0;
}