题解 SP16244 【KUSAC - Kusac】

一共有两种算法： ### 一 按照情况递归(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; } ```