g***9
发帖数: 159 | 1 给定一个非负整数a（不超过106），是否存在整数b，使得a和b的乘积全为1。如果存在
，返回最小的乘积的位数。如果不存在，返回-1。
样例：a=3，存在b=37，使得3*37=111，则函数应返回3（111的位数）。
求指点，感谢！ |
f****e
发帖数: 34 | 2 主要使用公式(x*10+1)%y=((x%y)*10+1)%y
比如a=3，你计算了11%3，马上就可以算出111%3,继续可以算出1111%3...
所以可以枚举1的位数，那要枚举多少位呢？最多a位，
因为x%a不会超过a，如果枚举过程中同一个模出现2次，那么根据上面的公式，就出现
循环节了，返回-1.
具体实现的时候可以开一个大小为a的bool数组
【在 g***9 的大作中提到】
: 给定一个非负整数a（不超过106），是否存在整数b，使得a和b的乘积全为1。如果存在
: ，返回最小的乘积的位数。如果不存在，返回-1。
: 样例：a=3，存在b=37，使得3*37=111，则函数应返回3（111的位数）。
: 求指点，感谢！
|
z***y
发帖数: 50 | 3 其实不需要额外来的bool数组.
int findMinAllOne(int a) {
if(a==0) return -1;
int num = 1;
int count = 1;
int r = num%a;
int t = 0;
while(r && t < a){
num = r*10+1;
r = num%a;
t++;
count++;
}
if(r) return -1;
return count;
}
【在 f****e 的大作中提到】
: 主要使用公式(x*10+1)%y=((x%y)*10+1)%y
: 比如a=3，你计算了11%3，马上就可以算出111%3,继续可以算出1111%3...
: 所以可以枚举1的位数，那要枚举多少位呢？最多a位，
: 因为x%a不会超过a，如果枚举过程中同一个模出现2次，那么根据上面的公式，就出现
: 循环节了，返回-1.
: 具体实现的时候可以开一个大小为a的bool数组
|
f****e
发帖数: 34 | 4 对，不过用数组标记一下的话 对于无界的情况可以尽早结束枚举。
【在 z***y 的大作中提到】
: 其实不需要额外来的bool数组.
: int findMinAllOne(int a) {
: if(a==0) return -1;
: int num = 1;
: int count = 1;
: int r = num%a;
: int t = 0;
: while(r && t < a){
: num = r*10+1;
: r = num%a;
|
