题解 P6536 【[COCI2013-2014#1] KUŠAČ】

Miller2019 · 2020-05-17 18:30:00 · 题解

题意：求把 \ n 根香肠切成 \ m 分所需的刀数。

思路：如果切的地方刚好在连接的地方，就可以减去一刀。先假设需要切 \ m-1 (本来的次数) 刀，然后再减去 \ n 和 \ m 的最大公约数(重叠的部分)，再加上末尾的一刀。所以说答案就是 \ m 减去 \ m , n 的最大公因数。

#include<stdio.h>
int gcd(int a,int b) //log(min(a,b))
{
    return b?gcd(b,a%b):a;
}
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    printf("%d",m-gcd(n,m));
    return 0;
}

蒟蒻橙后第 10 篇题解。