Ones

http://acm.pku.edu.cn/JudgeOnline/problem?id=2551

Description

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?


solving

0 <= n <= 10000 이고 2나 5로 나눠 떨어지지 않는 정수 n의 어떤 배수는 '1'만 으로 이루어져 있다고 한다. 예를 들어 n이 3인 경우 3의 배수의 111은 '1' 만으로 이루어져 있다.
정수 n이 주어졌을 때 이 정수의 배수 중 '1' 만으로 이루어진 숫자의 1의 갯수를 구하는 문제이다.

(a * b) mod c = ((a mod c) * (b mod c)) mod c 를 이용하면 쉽게 문제를 해결할 수 있다.
(a + b) mod c = ((a mod c) + (b mod c)) mod c 도 성립한다.

#include <cstdio> int main() { int n; int len; int num; while(scanf("%d", &n) > 0) { len = 1; num = 1; while (num % n) { num = (num%n)*10+1; len++; } printf("%d\n", len); } return 0; }