首页 > 代码库 > UVA10673 上下界问题
UVA10673 上下界问题
1 #include <iostream> 2 #include<cstdio> 3 using namespace std; 4 #define LL long long 5 LL a,b,m,n,d; 6 void ex_gcd(LL a,LL b,LL &x,LL &y,LL &d) 7 { 8 if(b==0){ 9 d=a,x=1,y=0;10 }11 else{12 ex_gcd(b,a%b,x,y,d);13 LL t=x;14 x=y,y=t-a/b*y;15 }16 }17 int main()18 {19 LL T;20 cin>>T;21 for(int i=0;i<T;i++)22 {23 LL x,y;24 cin>>x>>y;25 if(x%y==0){26 cout<<1<<‘ ‘<<y-1<<endl;27 }28 else{29 a=x/y,b=a+1;30 ex_gcd(a,b,m,n,d);31 cout<<m*x<<‘ ‘<<n*x<<endl;32 }33 }34 return 0;35 }
Theorem
For any two integers x and k there exists two more integers p and q such that:
<!--[if !vml]--><!--[endif]-->
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.
<!--[if !supportEmptyParas]--> <!--[endif]-->
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, <!--[if !vml]--><!--[endif]--> and <!--[if !vml]--><!--[endif]-->fit in a 64 bit signed integer.
对于这道题目来说,要注意上下界的问题,当x%k==0时,它的上界和下界是一样的,因为答案有多种,输出一个即可,所以此时将答案定位1和k-1即可。
在x%k!=0时,它的上界和下界相差1,那么很自然的想到它们的最大公约数为1,所以可以直接用扩展欧几里德算法。
当然因为x是最大公约数的x倍,所以最后答案要乘上x
代码如下: