g779 - 小億老師的幸運數字

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷給定的數字 N 是否為小億老師的幸運數字。一個數字被視為幸運數字，如果它可以被數字 K 整除，或者數字 N 包含數字 K。

解題思路

解題思路是先檢查 N 是否可以被 K 整除。如果可以，則輸出 "YES"。否則，遍歷 N 的每一位數字，檢查是否包含數字 K。如果包含，則輸出 "YES"。如果 N 既不能被 K 整除，也不包含數字 K，則輸出 "NO"。

複雜度分析

• 時間複雜度: O(log N) (因為 while 迴圈的次數與 N 的位數成正比，N 的位數約為 log N)
• 空間複雜度: O(1) (使用了常數額外的空間)

程式碼

#include <bits/stdc++.h>
using namespace std;
int n,m;
int main(){
	cin >> n >> m;
	if(n%m==0){
		cout << "YES";
	}
	else{
		while(n){
			if(n%10==m){
				cout << "YES";
				return 0;
			}
			n/=10;
		}
		cout << "NO";
	}
}