UVA 10673 Play with Floor and Ceil(拡張ユークリッド)
タイトル:
与えられたx,k,p,qは、
考え方:
http://blog.csdn.net/fioman/article/details/2455698拡張ユークリッド定理を用いてax+by=gcd(a,b);x,yには整数解があるに違いない.
ACコード
与えられた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;
}