Question

link

给定一个非负整数a（不超过10⁶），是否存在整数b，使得a和b的乘积全为1。如果存在，返回最小的乘积的位数。如果不存在，返回-1。

样例：a=3，存在b=37，使得3*37=111，则函数应返回3（111的位数）。

Solution

There’s 1 equation of mod operation, which is helpful:

(a * b) mod x = ((mx+a') * (nx+b')) mod x = (a' mod x) * (b' mod x) = (a mod x) * (b mod x)

i.e. (a * b) mod x = (a mod x) * (b mod x)

Altough I don’t understand why does it contribute to the incredibly short solution code posted below. I can’t solve this question, frankly speaking.

Code

int findMinAllOne(int a) {
    if (a < 0 || (a % 10) % 2 == 0 || a % 10 == 5)
        return -1;

    int ans = 1;
    for (int p = 1; p != 0; p %= a) {
        p = 10 * p + 1;
        ++ans;
    }
    return a == 1 ? ans - 1 : ans;
}