题目大意：给出x和k，求p*floor(x/k)+q*ceil(x/k)==x的一组解(p,q)。
不要相信题目最后所说的64位整数，这道题目用long long或int64的结果就是超时！改回long之后，AC！不多说了，就是考察扩展欧几里德算法。
以下是我的代码：
#include<stdio.h>
#include<math.h>
//#define LOCAL
#ifdef LOCAL
#include<time.h>
#endif
void gcd(long a,long b,long &d,long &x,long &y)
{
if(b==0){d=a;x=1;y=0;}
else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
long test;
scanf("%ld",&test);
while(test--)
{
long a,b,c,k,x,y,d;
scanf("%ld%ld",&c,&k);
a=(long)floor((double)c/k);
b=(long)ceil((double)c/k);
gcd(a,b,d,x,y);
x*=(c/d);
y*=(c/d);
printf("%ld %ld\n",x,y);
}
#ifdef LOCAL
printf("time = %.4lf\n",(double)clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
posted on 2010-02-07 14:32
lee1r 阅读(432)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论