🔗 UVA-11934 Magic Formula

tags: `暴力法(Brute Force)`

範例程式碼已於 UVA、瘋狂程設(CPE) 上皆測試通過。

題意

題目給出一個二次函數 $f(x) = ax^2 + bx + c$ ，以及一個除數 $d$ 和一個上限 $L$ 。要求計算從 $f(0)$ 到 $f(L)$ 中，有多少個函數值能被 $d$ 整除。

約束條件

$-1000 \leq a, b, c \leq 1000$
$1 < d < 1000000$
$0 \leq L < 1000$

思路：暴力法(Brute Force)

枚舉 $[0, L]$ 中的每個數 $x$ ，計算 $f(x)$ 的值，並檢查是否能被 $d$ 整除。若能被整除，則將答案 $ans$ 加一。

複雜度分析

時間複雜度： $\mathcal{O}(L)$
空間複雜度： $\mathcal{O}(1)$

while True:
    a, b, c, d, L = map(int, input().split())
    if all(x == 0 for x in [a, b, c, d, L]):
        break
    ans = 0
    for x in range(L+1): # [0, L]
        if (a * x * x + b * x + c) % d == 0:
            ans += 1
    print(ans)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int a, b, c, d, L, ans;
    while (cin >> a >> b >> c >> d >> L && (a || b || c || d || L)) {
        ans = 0;
        for (int x = 0; x <= L; ++x) {
            if ((a * x * x + b * x + c) % d == 0) ans++;
        }
        cout << ans << endl;
    }
}