題目大意：給出x和k，求p*floor(x/k)+q*ceil(x/k)==x的一組解(p,q)。
不要相信題目最后所說的64位整數(shù)，這道題目用long long或int64的結(jié)果就是超時！改回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 閱讀(451)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)學(xué)/數(shù)論