当前位置:网站首页>【练习-7】(Uva 10976)Fractions Again?!(分数拆分)
【练习-7】(Uva 10976)Fractions Again?!(分数拆分)
2022-07-06 09:26:00 【火焰车】
翻译:
输入正整数k,找到所有的正整数x≥y,使得
1 k = 1 x + 1 y \frac{1}{k}=\frac{1}{x}+\frac{1}{y} k1=x1+y1
这个题也是很有意思,搞一些提前的运算:
既然要求找出所有的x,y,枚举的对象自然也就是x,y了。可问题在于,枚举的范围如何?从1/12=1/156+1/13可以看出,x可以比y大很多。难道要无休止地枚举下去?当然不是。由于x≥y,有1/x ≤1/y,因此 1/k - 1/y ≤ 1/y,即 y≤2k。这样只需要在[k+1,2k]范围内枚举y,然后根据y尝试计算出x即可。
(内容来自紫书)
这也太好了!
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
int main()
{
int n;
while(cin>>n && n)
{
int cnt = 0;
for(int i=n+1;i<=2*n;i++)
if((i*n)%(i-n)==0)
cnt++;
cout<<cnt<<endl;
for(int i=n+1;i<=2*n;i++)
if((i*n)%(i-n)==0)
printf("1/%d = 1/%d + 1/%d\n",n,(i*n)/(i-n),i);
}
}
直接写两遍一边算cnt一边输出是因为我太懒了。。。可能有简单的方法??额应该差不多吧。
中间的判断思路是这样的:1/k = 1/x +1/y,也就是说 1/k - 1/y = 1/x就是满足条件的。
等式左边化简一下就是 y/ky - k/ky ==》 (y-k)/yk 也就是说只要这个式子能化简成 1/?就是满足条件的。
也就是 1/(yk/(y-k))的分母是个整数。也就是yk%(y-k) ==0
因此得到了代码中的那个算式。
总结:
这样算式的题,要用未知数来推出几个新的算式简化题目。
主要就是推式子,推不出来就完犊子了。。。
边栏推荐
猜你喜欢
Optimization method of path problem before dynamic planning
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
JS --- all knowledge of JS objects and built-in objects (III)
LeetCode#62. Different paths
学习记录:理解 SysTick系统定时器,编写延时函数
差分(一维,二维,三维) 蓝桥杯三体攻击
洛谷P1102 A-B数对(二分,map,双指针)
B - 代码派对(女生赛)
Learning record: Tim - Basic timer
MATLAB综合练习:信号与系统中的应用
随机推荐
Learning record: how to perform PWM output
Es6---es6 content details
Research Report on market supply and demand and strategy of geosynthetics industry in China
JS调用摄像头
Research Report on market supply and demand and strategy of China's medical chair industry
China's salt water membrane market trend report, technological innovation and market forecast
ucorelab4
JS --- detailed explanation of JS DOM (IV)
数据在内存中的存储&载入内存,让程序运行起来
Opencv learning log 14 - count the number of coins in the picture (regardless of overlap)
Record of brushing questions with force deduction -- complete knapsack problem (I)
初入Redis
Flex --- detailed explanation of flex layout attributes
LeetCode#118. Yanghui triangle
Research Report on market supply and demand and strategy of Chinese hospital cleaning chemicals industry
7-1 懂的都懂 (20 分)
Es6--- two methods of capturing promise status as failed
E. Breaking the Wall
Path problem before dynamic planning
Learning record: Tim - Basic timer