首页 > 代码库 > 【1008】How many n

【1008】How many n

题目:http://acm.hit.edu.cn/hoj/problem/view?id=1008

参考:http://hujianliu-tuo.blog.163.com/blog/#m=0&t=1&c=fks_087068085080081075083080083095085086087069086095086069086

这个题目看着觉得很简单,一上手就用穷举,把所有的数都一一给测一遍,但是到真正写的时候就会发现:不知道k的取值范围,还有如果一直举下去会有超时的情况发生,后面参考了上面链接的代码后,才发现可以避免这些问题;首先,如果一个数除以除数的余数在改变后能整除除数那么这个数就能整除除数;其次,不能整除则说明出现了无限循环,那么除的次数到一定大时还没有整除则表示有了循环的出现,多大呢?大于自己也是一个很好的选择;不过看有些人的代码居然只跑了0点几秒,很惊讶呀惊讶 谁有这样的代码记得给我看看哦 ~可怜可怜以后不能想到什么就是什么,多分析一下,很多情况都不需要暴力就能解决的

#include <iostream>



using namespace std;



int main()

{

int N,M;

while (cin >> N>>M)
{
int num = N,count = 1;
while ((num % M != 0) && (count <= 2*M))
{
    num = 10 * (num % M) + N;
        count ++;}

    if (count == 2*M+1)count = 0;

    cout <<count <<endl;

}

return 0;

}