如何用数学方法确定能被与10互质的n整除的最小纯1数及存在性？

一、m的存在性：必然存在 #

题目已给定n与10互质，根据欧拉定理：对于互质的整数a和n，有a^φ(n) ≡ 1 mod n，其中φ(n)是欧拉函数（表示小于等于n且与n互质的正整数的个数）。

全1数可统一表示为：
m_k = (10^k - 1) / 9
即k个1组成的数。我们需要m_k ≡ 0 mod n，等价于：
10^k ≡ 1 mod n

由于10和n互质，欧拉定理保证存在k=φ(n)满足该同余式，因此必然存在对应的m_k。只要n与10互质，就不存在无解的情况。

二、如何找到最小的m #

最小的m对应最小的k，这个k叫做10在模n下的乘法阶——即满足10^k ≡ 1 mod n的最小正整数k。求解步骤如下：

1. 计算n的欧拉函数φ(n)
2. 列出φ(n)的所有正约数，按从小到大排序
3. 对每个约数d，依次验证10^d ≡ 1 mod n，第一个满足条件的d就是最小的k，对应的m就是d个1组成的数。

举实际例子：

• 当n=37时，φ(37)=36（37是质数，质数的欧拉函数等于自身减1）。36的约数有1,2,3,4,6,9,12,18,36。验证：
  • 10^1 mod37=10≠1
  • 10^2=100 mod37=100-2*37=26≠1
  • 10^3=10*26=260 mod37=260-7*37=1 → 满足条件，因此k=3，m=111。

三、和你优化后代码的关联 #

你优化后的代码本质上是用迭代法找最小的k：

while(m%n!=0)
{
        m=(m*10+1)%n;
        cout<<"1";
}

每次迭代计算的是m_k mod n（m_k是k个1组成的数），因为：

• m₁=1 modn
• m₂=(m₁*10+1) modn
• m₃=(m₂*10+1) modn
  以此类推。当m_k modn=0时，此时输出的k个1就是最小的m。这种方法避免了大数溢出，同时每次计算的数值都小于n，效率远高于原始代码。

原始代码超时的核心原因是：当k很大时，m=(10^k-1)/9会快速超出long long的范围，导致计算错误或效率极低；而优化后的代码始终只保留模n的结果，计算量小且不会溢出。

内容的提问来源于stack exchange，提问作者user17286002