POJ 2551 Ones

题目描述：

Given any integer 0 <= n <= 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1's. How many digits are in the smallest such a multiple of n?

a multiple of n 的意思是某一个数与 n 的积（吧？）

开始我愣是没读懂题，一搜都说是水题，没看别人的题解，自己想了两种方法:

1. 试因子法：每次选取一个0-9的数字使积的最后一位变为1，当然要在乘的过程中更新积，这样做事先最好建一张表，map[i, j] 存储使 (i*k)%10=j 的k；

  稍显繁琐，下面的代码已A，0MS；

# include <stdio.h>

const int map[4][10] = { {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},    /* 1 */
                         {0, 7, 4, 1, 8, 5, 2, 9, 6, 3},    /* 3 */
                         {0, 3, 6, 9, 2, 5, 8, 1, 4, 7},    /* 7 */
                         {0, 9, 8, 7, 6, 5, 4, 3, 2, 1}};   /* 9 */

int solve(int n);

int main()
{
    int n;
    
    while (~scanf("%d", &n))
        printf("%d\n", solve(n));
    
    return 0;
}

int solve(int n)
{
    int cnt, t, r, c, x;
    
    t = 0;
    cnt = 0;
    r = (n % 10) / 3;          /* 1, 3, 7, 9 / 3 = 0, 1, 2, 3*/
    while (t != 1)
    {
        t = t / 10;
        x = t % 10;
        if (x != 1)
        {
            c = (x==0 ? 1:11-x);
            t = t + n * map[r][c];
        }
        ++cnt; 
    }
        
    return cnt;
}

2. 除法：首先选择最接近 n 的1序列，然后不断除，更新余数，也是0MS……这样做这题确实有点水。

# include <stdio.h>

const int s[] = {1, 11, 111, 1111, 11111};

int solve(int n);

int main()
{
    int n;
    
    while (~scanf("%d", &n))
        printf("%d\n", solve(n));
    
    return 0;
}

int solve(int n)
{
    int cnt, r;
    
    cnt = 0;
    while (s[cnt++] < n) ;
    r = s[cnt-1] % n;
    while (r != 0)
    {
        r = (r*10 + 1) % n;
        ++cnt;
    }
    
    return cnt;
}