마법의 구슬
시간 제한2초메모리 제한128 MB
S+F개 중 S개를 뽑는 조합의 수 C(S+F, S)를 M 이하에서 정확히 나누는 가장 큰 사람 수를, 큰 수를 직접 계산하지 않고 소수 지수 분석으로 구합니다.
문제
어떤 마법사는 진짜 마법의 구슬 S개와, 겉모습이 같은 가짜 구슬 F개를 만들었다. 진짜 구슬 S개가 모두 모이면 매우 강력한 힘을 낸다.
한 사람이 세계를 지배하기 위해 어떤 구슬이 진짜인지 알아내려 한다. 그는 N명의 사람을 모아, 전체 S+F개의 구슬 중 S개를 고르는 모든 조합을 한 번씩 테스트하게 하려고 한다.
각 사람에게는 미리 테스트할 조합들이 배정된다. 같은 조합은 최대 한 번만 테스트한다.
또한 모든 사람은 같은 개수의 조합을 테스트해야 한다. 모을 수 있는 사람의 수가 최대 M명일 때, M명을 넘지 않으면서 모든 조합을 빠짐없이 테스트하고 모든 사람이 같은 횟수만큼 일하게 할 수 있는 최대 사람 수를 구하라.
입력
첫째 줄에 S, F, M이 주어진다.
S와 F는 1 이상 1,000,000,000 이하의 정수이고, M은 1 이상 100,000 이하의 정수이다.
출력
조건을 만족하는 최대 사람 수를 출력한다. 불가능하다면 -1을 출력한다.
힌트
S=3, F=1이면 전체 구슬 4개 중 3개를 고르는 조합은 4개이다. 따라서 2명이 각각 2개의 조합을 테스트하도록 나눌 수 있다.