上海计算机学会 2021 年 2 月月赛 C++ C 组 T4 香肠切片
最编程
2024-05-05 09:25:32
...
题目描述
有 n 条香肠,每条香肠的长度相等。我们打算将这些香肠切开后分给 k 名客人,且要求每名客人获得一样多的香肠,且要将所有的香肠分配完,不做保留。
请问最少需要切几刀才能完成?一刀只能切断一条香肠,每一个客人都可以接受多段香肠。
输入格式
两个整数:n 与 k。
输出格式
单个整数:表示最少需要切几刀。
数据范围
- 对于 40%的数据,1≤n,k≤50;
- 对于 70%的数据,1≤n,k≤5000;
- 对于 100%的数据,1≤n,k≤5,000,000。
- 对于附加数据,1≤n,k≤10^15。
样例数据
输入:
2 6
输出:
4
说明:
两根香肠六人分,每根香肠切成3段,共4刀
输入:
6 2
输出:
0
说明:
六根香肠两人分,不需要切
输入:
3 4
输出:
3
说明:
在每根香肠的1/4处切开,有三人每人得到3/4根香肠,最后一人得到三个1/4长的香肠。
解析:
第一种方式:纯模拟
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
int ans=0;
cin >> n >> k;
if (n