励志用尽量少的代码做高效表达
Problem describe
It is easy to see that for every fraction in the form 1/k(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 given k?
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 (x, y) 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
题目(提交)链接——>UVa-10976
心路历程
题目不难理解，比较难的是如何更好的A掉，最近在备考蓝桥杯，因此十分注重对暴力枚举的理解和优化。
当n=9999时，暴力枚举显然可能超限，因此放弃。
观察样例时发现，由于有x>=y的规定，因此y的最大值只能是n/2。而y的最小只能取到n+1。这样，y的范围就出来了，接下来考虑x。
我们发现，如果y等于一个不合适的数，显然x增大到无限大也没办法得出解，因此得设法固定住x。
于是我将x设为未知数。很容易列出方程：
化简后得：
其中y、n已知，不难得出，x=(n*y)/(y-n)。
在y的遍历过程中，若x为整数，则说明有解，直接输出即可。
在编写代码过程中，我使用了两个动态数组vector，求长度、动态存储等更方便一些。
代码展示：
#include<bits/stdc++.h>
using namespace std;
int main() {int n; while(scanf("%d", &n) != EOF) {vector<int>v1, v2; //分别存储分子和分母 v1.clear(); v2.clear(); for(int i = n*2; i > n; i--) if((i*n)%(i-n)==0) {v1.push_back(i); v2.push_back((i*n)/(i-n)); } //输出 int len = v1.size();printf("%d\n", len);for(int i=(len-1); i>=0; i--) printf("1/%d = 1/%d + 1/%d\n", n, v2[i], v1[i]); }
return 0; }
总结：
数学是编程中非常重要的一环，虽然编程题中直接涉及的数学知识不算很多，但灵活的应用数学思想，绝对会使编程水平有质的提高。
如果这篇文章对你产生了帮助，就请给博主一个小小的赞吧！大家的点赞是我创作的最大动力！