葫芦岛市网站建设_网站建设公司_Node.js_seo优化

题目链接：100948. 最小全 1 倍数（中等）

算法原理：

解法：鸽巢原理+枚举

12ms击败58.05%

时间复杂度O(Logk)

由于枚举的数可能很大，所以咱们只需要记录余数即可

①其中2和5的倍数一定不能被整除，先判断

②最多枚举k次，如果k次都不能被整除，那么一定无解

答疑

Q1：为什么最多枚举k次呢？

因为余数的范围是[0,k-1]，再枚举必然存在余数重复，意味着死循环

Java代码：

class Solution { public int minAllOneMultiple(int k) { if(k%2==0||k%5==0) return -1; if(k==1) return 1; int ret=1; int rem=1; while(rem%k!=0){ rem=(rem*10+1)%k; ret++; //鸽巢原理：最多循环k次，实际不会走到这，k与10互质必有解 if(ret>k) return -1; } return ret; } }