题解 SP16244 【KUSAC - Kusac】
hicc0305
2018-10-04 15:32:48
一共有两种算法:
### 一
按照情况递归(x为木棒数,y为人数):1.当前x,y的gcd大于1,那么就递归gcd*get(x/gcd,y/gcd) 2.当前x>=y,递归get(x%y,y) 3.x<y,递归x+get(x,y-x)
代码如下
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int gcd(int x,int y)
{
if(x==0) return y;
return gcd(y%x,x);
}
int get(int x,int y)
{
if(x==0) return 0;
if(x==1) return y-1;
int g=gcd(x,y);
if(g>1) return g*get(x/g,y/g);
else if(x>=y) return get(x%y,y);
else return x+get(x,y-x);
}
int main()
{
scanf("%d%d",&n,&m);
printf("%d",get(n,m));
return 0;
}
```
### 二
可以知道,最后每个人拿到的长度一定是总长度除以人数,可以想象成原来你就有一根长度为总长的木棍,你本来分给n个人需要切n-1刀,已经有别人帮你切了几刀,那么那重复的几刀你就不用切了
代码:
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return (b?gcd(b,a%b):a);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll a,b;
int main()
{
scanf("%lld%lld",&a,&b);
printf("%lld",b-a*b/lcm(a,b));//b减去重复的导数
return 0;
}
```