自动搬运

查看原文

来自洛谷，原作者为

	Miller2019 求互关!|古人云：Miller2019竞有多弱？无人知之。|我只是一个只会刷红/水题的蒟蒻！|信息、数学、物理竞赛为什么都来害我啊！！！|已淡谷

搬运于2025-08-24 22:21:42，当前版本为作者最后更新于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 篇题解。