首页 > 代码库 > UVA - 10673 Play with Floor and Ceil
UVA - 10673 Play with Floor and Ceil
题目来源：http://vjudge.net/problem/viewProblem.action?id=19592
扩展欧几里得方程： ax+by=gcd(a,b)一定有解
把a=floor(x/k);b=ceil(x/k);floor,ceil分别为向下取余和向上取余。
p,q作为为新的未知数，x必定为gcd(a,b)*N
p‘=p/N,q‘=q/N,
原方程变为ap‘+bq‘=gcd(a,b);再通过扩展欧几里得算法求出p‘,q‘,N=x/gcd(a,b),再将N代入p‘=p/N中求出p,同样求出q
1 #include<stdio.h> 2 #include<math.h> 3 typedef long long LL; 4 void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y) 5 { 6 if(!b) {d=a;y=0;x=1;} 7 else{ 8 ex_gcd(b,a%b,d,y,x); 9 y-=x*(a/b);10 }11 }12 int main()13 {14 int t;15 scanf("%d",&t);16 while(t--){17 LL x,k,d,p,q;18 scanf("%lld%lld",&x,&k);19 LL a=floor(1.0*x/k);20 LL b=ceil(1.0*x/k);21 ex_gcd(a,b,d,p,q);22 p*=x/d;23 q*=x/d;24 printf("%lld %lld\n",p,q);25 }26 return 0;27 }
UVA - 10673 Play with Floor and Ceil
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。