UVA 10673 Play with Floor and Ceil(拡張ユークリッド)

2566 ワード

タイトル:
与えられたx,k,p,qは、这里写图片描述
考え方:
http://blog.csdn.net/fioman/article/details/2455698拡張ユークリッド定理を用いてax+by=gcd(a,b);x,yには整数解があるに違いない.
ACコード
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
void gcd(int a,int b,int& d,int& x,int& y) {
    if(!b) {
        d = a, x = 1, y = 0;
    }else {
        gcd(b, a%b, d, y, x);
        y -= x*(a/b);
    }
}
int main() {
    int T, a, b, d, p, q, x, k;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d",&x,&k);
        a = (int)floor((double)x / k);
        b = (int)ceil((double)x / k);
        gcd(a,b,d,p,q);
        p *= (x / d);
        q *= (x / d);
        printf("%d %d
"
,p,q); } return 0; }