跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
looking_up_at_the_starry_sky
»
codeforces_round
2020-2021:teams:looking_up_at_the_starry_sky:codeforces_round
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
====== Contest Info ====== date: 2020.7.11 23:05-01:05 (+1D) [[https://codeforces.com/contest/1372/problem/B|practice link]] ====== Solutions ====== ===== B. A Math Problem ===== **题目大意**:已知: $a+b=n$,求最小化 $lcm(a,b)$. **题解**: 令 $d=gcd(a,b), m=lcm(a,b)$ 由 $\ a\times b=d\times m,\ d|n$ 得到 $$m=\frac{a\times b}{d}=d\times a'\times b',\ a'+b'=\frac{n}{d}$$ 固定 $d$,最小化 $m$ 得 $a'=1, b'=\frac{n}{d}-1$,进而 $$m=d\times b'=d\times(\frac{n}{d}-1)=n-d$$ $$b'=\frac{n}{d}-1>0\Rightarrow d<n$$ 此时最大化 $d|n$ 且 $d<n$ 可得 $m$ 最小值. 综上$$m=n-\arg\max_{d<n} d|n$$ 时间复杂度 $\mathcal{O}(\sqrt{n})$.
2020-2021/teams/looking_up_at_the_starry_sky/codeforces_round.txt
· 最后更改: 2020/07/17 17:16 由
x342333349
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部