e598 - 傑出校友表揚

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個九位數的校友編號，要求判斷該編號是否為傑出校友。傑出校友的定義是其編號不能被其他可能的校友編號整除。

解題思路

由於校友編號是九位數，且第一位不為 0，因此可能的校友編號範圍是 100,000,000 到 999,999,999。題目要求判斷給定的編號是否能被其他編號整除。 程式碼中，只檢查了 2 到 9 是否能整除給定的編號，如果可以且商大於等於 1e8，則表示存在一個比給定編號小的編號可以整除它，因此不是傑出校友。 這個解法的核心思想是，如果一個數能被 2 到 9 中的任何一個數整除，且商大於等於 100,000,000，那麼它就不是傑出校友。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <bits/stdc++.h>
using namespace std;
int n,ba=1e8;
int main(){
	cin >> n;
	for(int i=2;i<10;++i){
		if(n%i==0&&n/i>=ba){
			cout << "no";
			return 0;
		}
	}
	cout << "yes";
}