백준 4375: 1 (JAVA) / 모듈러 연산 분배 법칙

https://www.acmicpc.net/problem/4375

4375번: 1

이 문제는 수학 문제이다. 나머지 연산자를 사용하여 단순히 계속 나누면 타임 아웃이 발생한다. 

이 문제를 풀려면 나머지 연산의 분배법칙에 대해 알아야 한다.

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

%연산은 위와 같은 분배 법칙이 성립한다. 

4375에 적용해보면 1, 11, 111, 1111, 11111, 111111...은 1, (10+1), (110+1), (1110+1), (11110+1)...으로 나타낼 수 있다.

 

예를 들면

111%3 = (110%3 + 1%3)%3으로 나타낼 수 있다.

따라서 이전에 구한 나머지 값에 10을 곱하고 1을 더한 후 a로 나눠주면 된다.

import java.util.*;

public class Main {
	public static void main(String[] args){
			int a, i;
			Scanner sc = new Scanner(System.in);
			
			int n=1;
			
			while(sc.hasNextInt()) {
				a=sc.nextInt();
				n=1;
				for(i=1; n%a!=0; i++)
				{
					n=(n*10)%a + 1;
					n%=a;
				}
				
				System.out.println(i);
			}
			
			
	  }
}