uva 10673 Play with Floor and Ceil

时间：2021-05-09 23:31:32

Problem A
Play with Floor and Ceil
Input: standard input
Output: standard output
Time Limit: 1 second

Theorem

For any two integers x and k there exists two more integers p and q such that:

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 you’d 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,  and fit in a 64 bit signed integer.

Sample Input                              Output for Sample Input

3

5 2

40 2

24444 6

1 1

1 1

0 6

Problem setter: Monirul Hasan, Member of Elite Problemsetters' Panel

Special Thanks: Shahriar Manzoor, Member of Elite Problemsetters' Panel

知道floor和ceil 就行。

floor向下取整 floor(1.9999) = 1;

同理。

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long LL;

 LL Ex_GCD(LL a,LL b,LL &x,LL& y)

 {

     if(b==)

     {

         x=;

         y=;

         return a;

     }

     LL g=Ex_GCD(b,a%b,x,y);

     LL hxl=x-(a/b)*y;

     x=y;

     y=hxl;

     return g;

 }

 int main()

 {

     LL T;

     LL a,b,c,g,x,y,n,m;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%lld %lld",&n,&m);

         a = (LL)floor(n/(double)m);/**向下取整floor(1.999) = 1  **/

         b = (LL)ceil(n/(double)m);

         c = n;

         g = Ex_GCD(a,b,x,y);

         x=x*(c/g);

         b=b/g;

         x=x%b;

         while(x<) x=x+b;

         c=c/g;

         y=(c-x*a)/b;

         printf("%lld %lld\n",x,y);

     }

     return ;

 }

相关文章