2016acmicpc现场赛大连赛区D题

110 阅读 0 评论 73 点赞

我是靠谱客的博主美好悟空，最近开发中收集的这篇文章主要介绍2016acmicpc现场赛大连赛区D题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

由原式可假设：k*x1+k*x2=a；k*x1*x2=b；

得

a=（x1+x2）*k；b=x1*x2*k；

得gcd（a,b）=k；很多人可能不懂这是为什么，这里我给出证明及结论

结论：x1与x2互质，则x1+x2与x1*x2互质

证明：反证法，假设x1+x2与x1*x2不互质，则意味着x1*x2与x1+x2有公因子，设为m，x1*x2=k1*m；x1+x2=k2*m；可以得出式子：x1=k1/x2*m；x2=（k2-x1）*m；可以看出，这样x1与x2都有一个公因子m，所以与一开始的条件x1与x2互质矛盾，所以x1*x2与x1+x2是互质的。

OK，证明完成，则原式a=（x1+x2）*k；b=x1*x2*k；k=gcd（a,b），这样2个方程，2个未知数，k，a，b已知，x1，x2可通过O（1）得解。

OK，这样基本完成了，再短短十几行代码，就能切D。