Petrozavodsk Winter Camp, Day 8, 2014, Fine Brochures

1的个数-块的个数+多减的个数+flag

多减的只会在一个循环末尾出现

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i) 
#define dwn(i, j, k) for (int i = int(j); i >= int(k); -- i)
typedef long long LL;
LL k, m, n;
LL gcd(LL a, LL b) {
    if (!b) return a; return gcd(b, a % b);
}
int main() {
    cin >> k >> m >> n;
    int flag = (k * m % n) >= k;
    if (n < k) {
        cout << 0 << '
'; return 0;
    }
    if (n == k || n >= 2 * k - 1) {
        cout << (k * m / n) + flag << '
';
        return 0;
    }
    LL block = k * m / n;
    LL one = block * n / k;
    if ((block * n) % k) one ++;
    LL cycle = k / (gcd(k, n));
    LL ans = one - block + block / cycle + flag;
    cout << ans << '
';
}