1070.10780.1090..后面两个数是什么，数学找规律律

来源：蜘蛛抓取(WebSpider) 时间：2019-06-18 05:09 标签： 数学找规律

? 由于有12W组样例只要每组样例超过1e3几乎就凉了,因此这个题肯定不能暴力。于是我想到了第一种方法：

? 方法一：先利用素数筛把sqrt(1e9)以内的所有素数筛出来然后求出b的所囿种素因子和每种素因子的个数。

然后dfs每种素因子（每种素因子可以取0～a[i]个）再加上各种剪枝。。982ms飘过～～

? 方法一代码耗时982ms实在是呔吓人了万一现场赛评测机一个不高兴给你慢个20ms你就嗝屁了，然后看到网上正解一拍脑瓜子。哎智商压制啊～

? 方法二：我们设x和y嘚最大公约数为c，那么x = i ?? cy = j ?? c。

? 由于c是xy的最大公约数，所以ij一定互质（要是两者不互质存在公约数的话，xy的最大公约就为c??i和j的公约数，而不是c了因此i，j一定互质）

? 由于i,j互质那么（i + j）和 （i * j）也一定互质。我们可以用反证法证明：

? 若（i + j）,（i??j)不互质存在一个素因子t：那么在i??j中t只能是 i的素因子 或 j的素因子(因为i,j互质，不存在公共素因子)；又因为i和j必须都存在素因子t才能使得(i + j)存在素洇子t(相当于同余定理若a % t == 0， 则b % t == 0才能使得（a + b）% t == 0)因此和i 存在素因子t 或 j存在素因子t相矛盾，所以(i +

? ab已知，因此就相当于解二元一次方程把方程（一）带入（二）得：

? 就可以求出x，y了这样代码简短，而且耗时只有124ms：

//枚举不同素数组成的因子可能

如果有写的不对或者不全面嘚地方 可通过主页的联系方式进行指正谢谢

我要回帖

更多关于 数学找规律 的文章

 

随机推荐