当前位置:网站首页>[exercise-7] (UVA 10976) fractions again?! (fraction split)
[exercise-7] (UVA 10976) fractions again?! (fraction split)
2022-07-06 15:56:00 【Flame car】
translate :
Enter a positive integer k, Find all positive integers x≥y, bring
1 k = 1 x + 1 y \frac{1}{k}=\frac{1}{x}+\frac{1}{y} k1=x1+y1
This question is also very interesting , Do some advanced calculation :
Since it is required to find all x,y, The enumerated object is naturally x,y 了 . But the problem is , How about the scope of enumeration ? from 1/12=1/156+1/13 It can be seen that ,x Comparable y Much larger . Should we enumerate endlessly ? Of course not. . because x≥y, Yes 1/x ≤1/y, therefore 1/k - 1/y ≤ 1/y, namely y≤2k. This only needs to be done in [k+1,2k] Enumeration in scope y, And then according to y Try to work out x that will do .
( Content from Purple Book )
That's great !
AC Code :
#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);
}
}
Write directly twice and calculate cnt One side of the output is because I'm too lazy ... There may be simple ways ?? Well, it should be about the same .
The middle judgment idea is like this :1/k = 1/x +1/y, in other words 1/k - 1/y = 1/x Is to meet the conditions .
The left side of the equation is simplified to y/ky - k/ky ==》 (y-k)/yk That is to say, as long as this formula can be reduced to 1/? Is to meet the conditions .
That is to say 1/(yk/(y-k)) The denominator of is an integer . That is to say yk%(y-k) ==0
So we get the formula in the code .
summary :
The problem of this formula , We should use unknown numbers to deduce several new formulas to simplify the problem .
Mainly push formula , If you can't push it out, you'll be finished ...
边栏推荐
- Accounting regulations and professional ethics [2]
- Cost accounting [14]
- 信息安全-威胁检测引擎-常见规则引擎底座性能比较
- 最全编程语言在线 API 文档
- STM32 learning record: LED light flashes (register version)
- 洛谷P1102 A-B数对(二分,map,双指针)
- Learning record: STM32F103 clock system overview working principle
- Research Report on market supply and demand and strategy of China's land incineration plant industry
- 7-1 懂的都懂 (20 分)
- China's PCB connector market trend report, technological innovation and market forecast
猜你喜欢
Matlab example: two expressions of step function
Essai de pénétration (1) - - outils nécessaires, navigation
Learning records: serial communication and solutions to errors encountered
Learning record: how to perform PWM output
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
力扣刷题记录
C语言学习笔记
Ball Dropping
Determine the Photo Position
随机推荐
【练习4-1】Cake Distribution(分配蛋糕)
F - Birthday Cake(山东省赛)
Penetration test (1) -- necessary tools, navigation
力扣刷题记录--完全背包问题(一)
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
Essai de pénétration (1) - - outils nécessaires, navigation
CS zero foundation introductory learning record
Cost accounting [13]
TCP的三次握手与四次挥手
Cost accounting [14]
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
【练习-6】(Uva 725)Division(除法)== 暴力
Accounting regulations and professional ethics [3]
基于web的照片数码冲印网站
Gartner:关于零信任网络访问最佳实践的五个建议
1010 things that college students majoring in it must do before graduation
Information security - security professional name | CVE | rce | POC | Vul | 0day
Cost accounting [14]
Ball Dropping
SSM框架常用配置文件