首页 > 代码库 > Uva10673 - Play with Floor and Ceil ( 扩展欧几里定理 )

Uva10673 - Play with Floor and Ceil ( 扩展欧几里定理 )

 

Uva10673 - Play with Floor and Ceil ( 扩展欧几里定理 ) 

 

实际上是一道很裸的扩展欧几里德定理的题目,结果把Floor和Ceil搞反了WA一次悲剧啊

#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long LL;void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y){    if(!b)    {        d = a;        x = 1, y = 0;        return;    }    else    {        ex_gcd(b, a%b, d, y, x);        y -= x * (a / b);        return;    }}void Orz(){    int cas = 0;    LL a, b, x, y, d, c, X, K ;    scanf("%d",&cas);    while(cas--)    {        scanf("%lld %lld",&X,&K);        //a = (LL)ceil(1.0*X/K);  搞反了,,擦         //b = (LL)floor(1.0*X/K);        a = (LL)floor(1.0*X/K);        b = (LL)ceil(1.0*X/K);        ex_gcd(a, b, d, x, y);        x = x * X / d;        y = y * X / d;        printf("%lld %lld\n",x,y);    }}int main(){    Orz();    return 0;}

 

Uva10673 - Play with Floor and Ceil ( 扩展欧几里定理 )