Boj 4375) Ones

문제

백준 4375

설명

위 문제의 답은 반드시 존재함.

• 1, 11, 111 … 111111 .. 이런 수열이 있다고 하자.
• 비둘기집 원리에 따라 위 수열중 주어진 수 x 로 나눈 나머지가 같은 두 항이 적어도 한개 이상 존재함.
• 두 항을 빼면 1111…1100..00 이런 꼴의 수가 되며 x 의 배수임
• 주어진 조건에 따라서 x 는 10의 배수가 아니므로 위에서 구한 두 항의 차에서 0 부분을 뺀 수도 x 의 배수임.
• -> 즉 이 수가 1로만 이루어진 x 의 배수임

시간 복잡도

O(1)

코드

int main()
{
	int x, t, cnt;
	while (1)
	{
		cin >> x;;
		if (cin.eof()) break;
		if (x == 1) {
			cout << "1\n";
			continue;
		}
		cnt = t = 1;
		while (t)
		{
			t = t * 10 + 1;
			t %= x;
			cnt++;
		}
		cout << cnt << '\n';
	}
}