Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1614
Theorem For any two integers x and k there exists two more integers p and q such that: x = p ⌊ x k ⌋ + q ⌈ x k ⌉ It’s a fairly easy task to prove this theorem, so we’d not ask you to do that. We’d ask for something even easier! Given the values of x and k, you’d only need to find integers p and q that satisfies the given equation. Input The first line of the input contains an integer, T (1 ≤ T ≤ 1000) that gives you the number of test cases. In each of the following T lines youd be given two positive integers x and k. You can safely assume that x and k will always be less than 108 . Output For each of the test cases print two integers: p and q in one line. These two integers are to be separated by a single space. If there are multiple pairs of p and q that satisfy the equation, any one would do. But to help us keep our task simple, please make sure that the values, p ⌊ x k ⌋ and q ⌈ x k ⌉ fit in a 64 bit signed integer.
Sample Input 3 5 2 40 2 24444 6
Sample Output 1 1 1 1 0 6
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int x,y,d;
// ax + by = d
// store x, y, and d as global variables
void extendedEuclid(int a, int b) {
if (b == 0) { x = 1; y = 0; d = a; return; } // base case
extendedEuclid(b, a % b); // similar as the original gcd
int x1 = y;
int y1 = x - (a / b) * y;
x = x1;
y = y1;
}
int main() {
int x1,k,t;
scanf("%d",&t);
while(t--) {
scanf("%d %d",&x1,&k);
int a = x1/k, b = (int)ceil((double)x1/k);
extendedEuclid(a,b);
// ax + by = d
// to get to x1, we multiply whole equation by x1/d
x *= x1/d;
y *= x1/d;
printf("%d %d\n",x,y);
}
}
Input
5 2
40 2
24444 6
Output
1 1
0 6
Demonstration
UVA Online Judge solution - 10673-Play with Floor and Ceil UVA - Online Judge solution in C,C++,java