此文章可以使用目录功能哟↑(点击上方[+])
HDU 5924 Mr. Frog’s Problem
Accept: 0 Submit: 0
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 A≤C≤B,A≤D≤B and A/B+B/A≤C/D+D/C.
Input
first line contains only one integer T (T≤125), which indicates the number of test cases. Each test case contains two integers A and B (1≤A≤B≤10^18).
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
10 10
9 27
Sample Output
1
10 10
Case #2:
2
9 27
27 9
Problem Idea
解题思路:
【题意】
给你两个正整数A和B
要求找出所有的整数对(C,D)
满足A≤C≤B,A≤D≤B且A/B+B/A≤C/D+D/C
【类型】
数学证明
【分析】
网上的很多题解貌似都直接说是规律就完事了
作为一个合格的Acmer,我们应该要纠结一下为什么
∵C/D+D/C是对称的
∴我们不妨假设D≥C
为了简化运算,我们令D=C+k(k≥0)
由上式可知,当k越大,C越小时,D/C+C/D越大
∵A≤C≤B
∴C(min)=A
此时,当k达到最大时,即为D(max)=B
而该情况下,C/D+D/C恰好等于A/B+B/A
故满足A/B+B/A≤C/D+D/C的解仅有A==C&&B==D||A==D&&B==C
而当A==B时,解唯一,即A==B==C==D
【时间复杂度&&优化】
O(1)
题目链接→HDU 5924 Mr. Frog’s Problem
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
int main()
{int t,p=1;__int64 A,B;scanf("%d",&t);while(t--){scanf("%I64d%I64d",&A,&B);printf("Case #%d:\n",p++);if(A!=B)printf("2\n%I64d %I64d\n%I64d %I64d\n",A,B,B,A);elseprintf("1\n%I64d %I64d\n",A,B);}return 0;
}