分数拆分( Fractions Again, UVA 10976)-ACM

简介: It is easy to see that for every fraction in the form  (k > 0), we can always find two positive integers x and y,x ≥ y, such that:  .

 

It is easy to see that for every fraction in the form  (k > 0), we can always find two positive integers x and y,x ≥ y, such that: 

.

Now our question is: can you write a program that counts how many such pairs of x and y there are for any givenk?

Input

Input contains no more than 100 lines, each giving a value of k (0 < k ≤ 10000).

Output

For each k, output the number of corresponding (xy) pairs, followed by a sorted list of the values of x and y, as shown in the sample output.

Sample Input

2
12

Sample Output

2
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4
8
1/12 = 1/156 + 1/13
1/12 = 1/84 + 1/14
1/12 = 1/60 + 1/15
1/12 = 1/48 + 1/16
1/12 = 1/36 + 1/18
1/12 = 1/30 + 1/20
1/12 = 1/28 + 1/21
1/12 = 1/24 + 1/24


这个题目做起来不难,难点在数值精度到问题上,我是参照了这为朋友到讲解

http://www.2cto.com/kf/201111/111420.html

 

/*
 * FractionAgain.cpp
 *
 *  Created on: 2014-8-27
 *      Author: root
 */

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
bool isInt(double n){
	double c = n-(int)n;
	if(n >= 0){
		if( c < 1e-15 || c < -0.999999999999999 ) {
			//单精度对应1e-6和6个9,双精度对应1e-15和15个9
			return true;
		}
		else{
			return false;
		}
	}
	else{
		 if( -c < 1e-15 || -c < -0.999999999999999 ){
			 return true;
		 }
		 else{
			 return false;
		 }
	}

}

int main(){

	long  k ;
	vector<string> ans;
	char str[100];
	while((cin>>k)  && k != 0){
		long  max = k << 1;
		int y;
		ans.clear();
		for ( y = k + 1; y <= max; ++y) {
			double  x = (double)(k*y)/(y - k);
			if(isInt(x)){
				sprintf(str,"1/%ld = 1/%d + 1/%d\n",k,(int)x,y);
				ans.push_back(str);
			}

		}
		int size = ans.size();
		cout<<size<<endl;
		for (y = 0;y < size;y++) {
			cout<<ans[y];
		}
	}

	return 0;
}



 

目录
相关文章
|
机器学习/深度学习 自然语言处理 安全
将入学考试题搬进中文大模型数据集,20477道题目,还带4个候选答案
将入学考试题搬进中文大模型数据集,20477道题目,还带4个候选答案
185 0
|
算法
ACM算法训练【二进制中1的个数】
3.lowbit(x)运算 返回x二进制表示的最后一位1
54 1
ACM算法训练【二进制中1的个数】
|
算法 Python
Python算法之动态规划(Dynamic Programming)解析:二维矩阵中的醉汉(魔改版leetcode出界的路径数)
现在很多互联网企业学聪明了,知道应聘者有目的性的刷Leetcode原题,用来应付算法题面试,所以开始对这些题进行“魔改”,比如北京某电商平台的这道题: 有一个正方形的岛,使用二维方形矩阵表示,岛上有一个醉汉,每一步可以往上下左右四个方向之一移动一格,如果超出矩阵范围他就死了,假设每一步的方向都是随机的(因为他是醉的),请计算n步以后他还活着的概率。
Python算法之动态规划(Dynamic Programming)解析:二维矩阵中的醉汉(魔改版leetcode出界的路径数)
ACM训练题目【糖果传递】
ACM训练题目【糖果传递】
66 0
ACM训练题目【糖果传递】
|
算法 C++
ACM算法训练【第k个数】
ACM算法训练【第k个数】
44 0
ACM算法训练【第k个数】
|
算法
ACM算法训练【逆序对的数量】
ACM算法训练【逆序对的数量】
93 0
ACM算法训练【逆序对的数量】
|
编译器
PAT (Basic Level) Practice (中文)- 1077 互评成绩计算(20 分)
PAT (Basic Level) Practice (中文)- 1077 互评成绩计算(20 分)
105 0
|
Java Python
ACM 选手图解 LeetCode 搜索旋转排序数组Ⅱ
ACM 选手图解 LeetCode 搜索旋转排序数组Ⅱ
ACM 选手图解 LeetCode 搜索旋转排序数组Ⅱ
|
Java Python
ACM 选手图解 LeetCode 搜索旋转排序数组
ACM 选手图解 LeetCode 搜索旋转排序数组
ACM 选手图解 LeetCode 搜索旋转排序数组