题目分析

我们需要找到一个由全1组成的数字（如1, 11, 111,...），使其是给定整数$n$的倍数。题目要求输出这个最小全1数字的位数。

解题思路

1. 数学转换：

   • 全1数字可以表示为$\frac{10^k - 1}{9}$，其中$k$是位数。
   • 我们需要找到最小的$k$，使得$\frac{10^k - 1}{9} \equiv 0 \pmod{n}$。
   • 这等价于$10^k \equiv 1 \pmod{9n}$。

2. 模运算优化：

   • 直接计算$10^k$会很大，我们利用模运算性质：$(a \cdot b) \mod n = [(a \mod n) \cdot (b \mod n)] \mod n$。
   • 通过迭代计算$10^k \mod 9n$，直到结果为1。

代码

#include <iostream>
using namespace std;  
int main()
{
	int n;
	while(cin>>n)
	{
		int js=1;
		int tmp=1;
		while(tmp!=0)
		{
			tmp=tmp*10+1;
			tmp=tmp%n;
			js++; 
		}
		cout<<js<<endl;
	}
	return 0;
}