• 周四. 6月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CF1444A Division

admin

11月 28, 2021

A-Division

题目叙述

给你一个数 (x) 和一个数 (y) ,求最大的是 (x) 的因数不是 (y) 的因数的数。(xle 10^{18},yle 10^9)

题解

考虑到 (y) 比较小,给他分解质因数。只要存在一个质因数满足 (a) 在这个质因子上的次幂没有 (y) 多,那么 (a) 一定不是 (y) 的倍数。所以枚举每个质因子,看哪个没有 (y) 多,其他的全取最大就行了。

idea

  • 其实这种问题直接给他分解质因数一般来说很有用。

发表评论

您的电子邮箱地址不会被公开。