题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5924
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
One day, you, a clever boy, feel bored in your math class, and then fall asleep without your control. In your dream, you meet Mr. Frog, an elder man. He has a problem for you.
He gives you two positive integers A and B, and your task is to find all pairs of integers (C, D), such that and
Input
first line contains only one integer T (), which indicates the number of test cases. Each test case contains two integers A and B ().
Output
For each test case, first output one line "Case #x:", where x is the case number (starting from 1).
Then in a new line, print an integer s indicating the number of pairs you find.
In each of the following s lines, print a pair of integers C and D. pairs should be sorted by C, and then by D in ascending order.
Sample Input
2
10 10
9 27
Sample Output
Case #1:
1
10 10
Case #2:
2
9 27
27 9
Problem solving report:
Description: 给你两个正整数A和B,要求找出所有的整数对(C,D)满足:A≤C≤B,A≤D≤B且A/B+B/A≤C/D+D/C。
Problem solving: 因为C/D+D/C是对称的,所以我们不妨假设D≥C,故可令D=C+e,(e>=0)
为了简化运算,我们令D=C+k(k≥0),即C=D-k,
因由上式可知,当k越大时,C/D+D/C越大,而k又是D与C的差值,故当C=min(C)=A,D=max(D)=B时,k才是最大的,此时C/D+D/C达到最大,等于A/B+B/A,即C/D+D/C的最大值为A/B+B/A,故满足A/B+B/A≤C/D+D/C的情况只有A/B+B/A=C/D+D/C这种情况,故满足A/B+B/A≤C/D+D/C的解仅有A==C&&B==D||A==D&&B==C,而当A==B时,解唯一,即A==B==C==D。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int t, kase = 0;
long long A, B;
scanf("%d", &t);
while (t--) {
scanf("%lld%lld", &A, &B);
printf("Case #%d:\n", ++kase);
if (A != B) {
puts("2");
if (A > B)
swap(A, B);
printf("%lld %lld\n", A, B);
printf("%lld %lld\n", B, A);
}
else printf("1\n%lld %lld\n", A, B);
}
return 0;
}