[itint5]两数积全为1 - 阿牧遥 - 博客园

[itint5]两数积全为1 - 阿牧遥 - 博客园
https://github.com/AnnieKim/ITint5/blob/master/018_%E4%B8%A4%E6%95%B0%E7%A7%AF%E5%85%A8%E4%B8%BA1.cpp
 给定一个非负整数a（不超过106），是否存在整数b，使得a和b的乘积全为1。
 如果存在，返回最小的乘积的位数。如果不存在，返回-1。
 样例：a=3，存在b=37，使得3*37=111，则函数应返回3（111的位数）。
 Solution: 该方案来自问答区。
           首先根据个位数字判断是否存在这样的数，其次根据模运算的性质避免大数运算。
*/

int findMinAllOne(int a)
{
    int M[] = {0, 1, 0, 1, 0, 0, 0, 1, 0, 1};
    if (M[a % 10] == 0) return -1;

    int count = 1;
    for (int i = 1; i > 0; i %= a)
    {
        i = i * 10 + 1;
        count++;
    }
    return a == 1 ? 1 : count;
}
Status API Training Shop Blog About Pricing

这一题，首先如果直接去算的话，很容易就超出int或者long的表示范围了。那么要利用%的性质，(num * 10 + 1) % a = 10 * (num % a) + 1 % a。除了a为1的情况，都是10 * (num % a) + 1。然后计算的时候，先去掉是2和5的倍数的情况。也可以直接做，如果余数出现过，就不用继续了。

int findMinAllOne(int a) {

    if (a % 2 == 0 || a % 5 == 0) return -1;

    if (a == 1) return 1;

    int num = 1;

    int ans = 1;

    while (true) {

        if (num % a == 0) {

            return ans;

        } else {

            num %= a;

            num = num * 10 + 1;

            ans++;

        }

    }

}

https://github.com/ralphite/ITint5-Answers-Java/blob/master/%E4%B8%A4%E6%95%B0%E7%A7%AF%E5%85%A8%E4%B8%BA1.java
    public int findMinAllOne(int a) {
        if(a <= 0) {
            return -1;
        }
        int d1 = a % 10;
        if(!(d1 == 1 || d1 == 3 || d1 == 7 || d1 == 9)) {
            return -1;
        }
        HashSet<Integer> reminders = new HashSet<Integer>();
        int r = 0;
        int len=0;
        while(true) {
            r = r*10+1;
            len++;
            r = r%a;
            if(r == 0) {
                return len;
            }
            if(reminders.contains(r)) {
                return -1;
            }
            reminders.add(r);
        }
     
    }
http://lixinzhang.github.io/itint5-mian-shi-ti-zong-jie.html

一开始，想着正向的方式去枚举质数，然后检验乘积为111*11，发现无论时间规模或者空间规模都不行。

于是，考虑反向枚举111*111，因为这个的候选集合是非常少的。

然后，另一个需要解决的问题是，枚举111*111，但很容易超出数据类型范围。因此，枚举过程中，可以适当的减少候选值的规模，因为X%b的结果等价于(X−X/b∗b)结果。因此，在迭代过程中，可以逐渐减少数据大小范围。

int findMinAllOne(int a) {
    if (a == 0 || a % 5 == 0 || a % 2 ==0) return -1;
    int base = 1;
    int result = 1;
    while(true){
        if (base % a == 0) return result;
        base = base * 10 + 1;
        if (base > a) base = base - base/a * a;
        result++;
    }
    return -1;
}

Read full article from [itint5]两数积全为1 - 阿牧遥 - 博客园