Boj 1188) 음식평론가

문제

백준 1188

설명

소세지 전체를 하나로 볼 때, 소세지가 나누어지는 지점을 생각하면

• \(0 < t \leq M\) 를 만족하는 자연수 \(t\) 에 대해 \(t \cfrac {N}{M}\) 임.

이 지점이 자연수로 나타낼 수 없는 경우 잘라내야하고 나타낼 수 있는 경우 냅두면 됨.

• 위 지점을 자연수로 나타낼 수 있는 \(t\) 는 \(\cfrac {M}{gdc(N, M)}\) 의 배수임.
• 이를 만족하는 \(t\) 의 갯수는 \({M} / (\cfrac{M}{gdc(N, M)})\) 이 됨
• 따라서 \(M - gdc(N, M)\) 번 잘라내게 됨..

시간 복잡도

O(\(\log{(n+m)}\))

코드

int main(){
	int N, M;
	scanf("%d%d", &N, &M);
	printf("%d\n", M - M / (M / gcd(N, M)));
	return 0;
}