浙江财经大学
信工学院ACM集训队

HDU 5924 Mr. Frog’s Problem

本文由 Ocrosoft 于 2016-10-06 19:24:55 发表

Mr. Frog’s Problem

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 AB+BA≤CD+DC
 

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≤1018).
 

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
 

Solution
就知道用longlong坑人。
题意:给出n和m,要求找到n<=a,b<=m,使得a/b+b/a>=n/m+m/n。
思路:应该是可以推出,n<a,b<m,a/b+b/a<n/m+m/n,所以答案就是n m或者m n,只有相等才会取到相等,其他都是小于。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 100000 + 10;
const int MOD = 100000;
const double eps = 1e-6;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
//or2..or2..or2..or2..or2..//
int main()
{
	int n, cas = 1; cin >> n;
	while (n--)
	{
		LL a, b; cin >> a >> b;
		if (a > b)printf("Case #%d:\n0\n", cas++);
		else if (a == b)printf("Case #%d:\n1\n%I64d %I64d\n", cas++, a, b);
		else printf("Case #%d:\n2\n%I64d %I64d\n%I64d %I64d\n", cas++, a, b, b, a);
	}
	return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 5924 Mr. Frog’s Problem

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址