a993 - 10127 - Ones

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出對於給定的正整數 n (0 <= n <= 10000)，其最小的倍數由全為 1 的數字組成。輸出這個倍數的位數。

解題思路

對於給定的 n，我們需要找到最小的正整數 k，使得 11...1 (k 個 1) 可以被 n 整除。由於 n 不可被 2 或 5 整除，因此 n 與 10 無公因數。 程式碼使用模擬的方式，逐步建立由 1 組成的數字，並計算其除以 n 的餘數。當餘數為 0 時，表示找到了 n 的倍數，此時的位數即為答案。 具體來說，程式碼從 b = 1 和 c = 1 開始，每次將 b 乘以 10 再加 1，然後取 b 除以 n 的餘數。c 記錄了目前 b 的位數。這個過程持續進行，直到 b 除以 n 的餘數為 0。

複雜度分析

• 時間複雜度: O(n) 在最壞情況下，需要迭代 n 次才能找到答案。
• 空間複雜度: O(1) 程式碼只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,c;
	while(cin >> a){
		long long int b=1;
		c=1;
		while(b%a!=0){
			c++;
			b=b*10+1;
			b=b%a;
		}
		cout << c << "\n";
	}
}