HIT ACM1008 How many N

HIT ACM1008 How many N

问题描述

• Find a minimal interger K which is merely comprised of N and can be divided by M.
  For example,11 is the minimal number that and be divided by 11, and it is comprised of two '1’s, and 111111 can be divided by 13 which is comprised of six '1’s.
• K个数字N组成的数，能够被M整除。例如，2个1组成11，11能够被11整除。寻找最小的整数K。
• 输入：N，M，输出K。

分析

• K 个N组成数n， n = N + N ∗ 1 0 1 + N ∗ 1 0 2 + . . . + 1 0 k − 1 = 1 0 k − 1 9 n=N+N*10^1+N*10^2+...+10^{k-1}=frac{10^k-1}{9} n=N+N∗101+N∗102+...+10k−1=910k−1​
• 等价于 ( 1 0 k − 1 9 ) ∗ N ≡ 0 ( m o d M ) (frac{10^k-1}{9})*Nequiv0(mod M) (910k−1​)∗N≡0(modM)
• 首先想到，设 x = 1 0 k x=10^k x=10k,然后利用扩展欧几里得算法求解模线性方程 ( x − 1 9 ) ∗ N ≡ 0 ( m o d M ) (frac{x-1}{9})*Nequiv0(mod M) (9x−1​)∗N≡0(modM)的解，即： ( x − 1 9 ) ∗ N (frac{x-1}{9})*N (9x−1​)∗N能够整除 M M M，
  即： ( x − 1 9 ) (frac{x-1}{9}) (9x−1​)能够整除 M / g c d ( M , N ) M/gcd(M,N) M/gcd(M,N), g c d ( M , N ) gcd(M,N) gcd(M,N)是求M和N的最大公约数；
• x x x等于解的最小值。
• ( x − 1 9 ) (frac{x-1}{9}) (9x−1​)是 1,K个1；
• 原问题转换为， 1多少个1能够整除 g c d ( M , N ) gcd(M,N) gcd(M,N)
• 11111…1111能整除不含因数2和5的任何数。

程序流程

1. 显然，若 g c d ( M , N ) gcd(M,N) gcd(M,N) 能够整除2 或者整除5，则K不存在。
2. 对于 g c d ( M , N ) gcd(M,N) gcd(M,N) 不能够整除2 或者整除5的情况，不断增加1的个数，判断能否整除，则第一个即是最小的K值。
3. 为了避免计算过程中1的数目太多，降低运算速度，则再每次增加1，判断之后，对 g c d ( M , N ) gcd(M,N) gcd(M,N)进行取余操作，显然，这不影响下一次判断是否能够整除k.ca

代码

#include <stdio.h>
int gcd(int a,int b)
{///递归求最大公约数 欧几里得算法if(a%b == 0)return b;elsereturn gcd(b,a%b);
}
int main()
{int n, m;while(scanf("%d%d", &n, &m) != EOF){m = m / gcd(n, m);if (m % 2 == 0 || m % 5 == 0){printf("0n");continue;}int k = 1;int num = 1;while (num % m != 0 && k <= m){num = num % m;num = 10 * num + 1;k++;}printf("%dn", k);}return 0;
}