j031 - 11934 - Magic Formula

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個二次函數 f(x) = ax^2 + bx + c，一個除數 d 和一個極限值 L。要求計算在 [0, L] 範圍內，有多少個 f(x) 的值可以被 d 整除。

解題思路

題目要求計算 f(x) = ax^2 + bx + c 在 [0, L] 範圍內能被 d 整除的 x 的個數。由於 L 的範圍較小 (L < 1000)，可以直接迴圈遍歷 x 從 0 到 L，計算每個 x 對應的 f(x) 值，然後判斷 f(x) 是否能被 d 整除。如果能被整除，則計數器加一。

複雜度分析

• 時間複雜度: O(L)，其中 L 是輸入的極限值。迴圈遍歷 0 到 L，每次計算 f(x) 的值，因此時間複雜度與 L 成線性關係。
• 空間複雜度: O(1)，程式碼只使用了常數個變數，不隨輸入大小變化，因此空間複雜度為常數。

程式碼

#include <iostream>
using namespace std;
long long a,b,c,d,e;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	while(cin >> a >> b >> c >> d >> e){
		if(a||b||c||d||e){
			int ans=0;
			for(int i=0;i<=e;++i)
				if((a*i*i+b*i+c)%d==0)++ans;
			cout << ans << "\n";
			continue;	
		}
		return 0;
	}
}