c언어 4375번 1 (백준)

#include <stdio.h>

int main(void) {
	int d; //입력을 받을 변수
	while(~scanf("%d", &d)) { //scanf는 인자 한개를 입력 받으면 1을 return하며, EOF을 입력받으면 -1을 리턴합니다.
		long long int i = 1; //1 -> 11 -> 111 -> 1111.... 을 목적으로 만든 변수입니다.
		int cnt = 1; //자릿수를 나타내는 변수입니다.
		for( ; i%d; cnt++, i=(i*10+1)%d); //나누어질때까지 반복합니다.
		printf("%d\n", cnt); //자릿수를 출력합니다.
	}
}

풀이 : 수학

 

long long i을 만든 이유는 1 -> 11 -> 111 -> 1111... 을 위해서지만, overflow가 일어날 확률이 높습니다.

그러므로 위에(그림) 3으로 1로만 이루어진 배수중 가장 작은 것을 나누는 것을 보면,

 

왼쪽의 나누기는

오른쪽의 나머지가 0이 될 때까지,  (3으로 나누고, 나머지에 10을 곱한 후 1을 더하기) 이 과정을 거친 것과 같다는 것을 알 수 있습니다.

 

고로 반복을 하면서 i의 값을 i = (i*10+1)%입력받은값    으로 갱신해주면서, 나머지가 0이 될 때까지 반복해준후, 반복한 만큼을 출력해주면 됩니다. (계속 나머지를 이용하기 때문에, overflow의 위험이 없습니다)

 

또한 scanf()는 EOF을 입력받으면 -1을  return합니다.

-1  0xFFFFFFFF -> 11111111 11111111 11111111 11111111(2) 이므로 이를 not 비트연산을 하면

00000000 00000000 00000000 00000000 0이 됩니다.

 

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

4375번: 1