POJ 2551 Ones 简单的数论

题目所求为。给定一个n,求数列 { 1, 11, 111, 1111… } 第几项可以整除n。

设 x 整除 n,即 x % n == 0。

考虑到: 若 a + b = x,则 x % n == a %n + b % n。。这种奇怪的定理,

于是可以由 x = 1 % n 开始,每次 x = (x * 10 + 1) % n。直到 x %n 为0时,即为这个数。

# include <iostream>
using namespace std;

int n;

int main()
{
    while ( cin >> n )
    {
        int m = 1, c = 1;
        while ( m % n )
        {
            m = (m*10 + 1) % n ;
            ++c;
        }
        cout << c <<endl;
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>