2025 - 电梯诡谈
时间限制 : 1 秒
内存限制 : 128 MB
九号楼电梯经常性出问题，有时候关不上，有时候又不停，甚至有时候还不能一层一层地走，现在，某位胆小的同学在1楼不幸碰到了电梯故障，电梯每次只能向上移动a层或者向下移动b层，该同学吓尿了，但更不敢走楼梯，于是他要想办法用最少的次数移动到想到的楼层，假设楼层没有上限也没有下限，聪明的你能最多给他提供多少种方案呢？
题目输入
输入包含多组样例，每组一行，包含他想到达的楼层数m(1<m<=30)，电梯上行层数a（1<=a<=30）和电梯下行层数b(1<=b<=30，当m，a，b全为0时结束输入。
题目输出
输出对应每组样例，每组占一行，如果能到达则输出最多方案数，否则输出“dead”。
输入/输出样例
输入格式
6 2 1 3 10 1 3 3 3 0 0 0
输出格式
4 9 dead
C++解答
#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #include <vector> #include <string> #define maxn 40000 using namespace std; long long c[62][62]; void initc() { int i,j; for (i=0;i<=60;i++) for (j=0;j<=i;j++) { if (!j||i==j) c[i][j]=1; else c[i][j]=c[i-1][j-1]+c[i-1][j]; } return; } long long gcd(long long a,long long b) { if(b==0) return a; return gcd(b,a%b); } long long exgcd(long long a,long long b,long long &x,long long &y) { if(b==0) { x=1; y=0; return a; } long long ans=exgcd(b,a%b,x,y); long long tmp=x; x=y; y=tmp-a/b*y; return ans; } int main() { //freopen("test.in","r",stdin); //freopen("test.out","w",stdout); initc(); long long m,a,b; while(scanf("%lld%lld%lld",&m,&a,&b)!=EOF) { if(m==0 && a==0 && b==0) break; if((m-1)%gcd(a,b)!=0) { printf("dead\n"); continue; } long long x,y,g=gcd(a,b); long long cc=(m-1)/g; a/=g,b/=g; exgcd(a,b,x,y); x*=cc; x%=b; y=(cc-a*x)/b; while(x<0||y>0) { x+=b; y=(cc-a*x)/b; } y*=-1; printf("%lld\n",c[x+y][y]); } return 0; }