음식 평론가

math, divide

출처: BOJ 음식 평론가

SOL)
길이 1짜리 소시지를 일열로 쭉 이어 놓고 생각을 하면
총길이가 n짜리인 소시지가 나올 것이다.
이것을 이제 m등분하는 것이다.
즉 최소 m-1번 보다는 답이 커질 수 없다.

*그런데 n/m 길이 만큼 컷팅을 하는데
이미 잘려있는 곳을 또 자르는 경우가 있다.
이것을 찾아내어 답에서 -1을 빼준다.

n/m = (등분해야 할 길이)

(n/m) x i = (현재 확실히 컷팅한 길이)

n x i = m(현재 확실히 컷팅한 길이)

여기서 현재 확실히 컷팅한 길이가 정수형태가 나오면
이미 처음부터 잘려진 길이이다.
그래서 (n x i) % m == 0이면 답에서 1을 빼준다.


[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);


int main(){
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;

    if (n % m == 0) cout << 0;
    else {
        if (n > m) n -= m;
        int ans = m;
        for (int i = 1; i <= m; i++){
            if (i *n % m == 0) ans--;
        }
        cout << ans;
    }

    return 0;
}