2020牛客暑期多校第九场

2020牛客暑期多校第十场

无

AtCoder Grand Contest 047

见本周推荐

无

无

无

无

无

见本周推荐

AtCoder:

Integer Product

题意:

给一堆浮点数,问有哪些数对,它们的积是整数.

tag:

数学

题解:

显然,每个数可以看做是2的次幂乘以5的次幂再乘以其他的因数.因为要求两数之积是整数,所以只需要考虑2和5的贡献.

如果一个数的2和5的次幂分别是$x$,$y$,另一个数是$x'$,$y'$,如果有$x+x' \geq 0$,$y+y' \geq 0$,那么两个数的乘积就是整数.

只需要把每个数先补成整数,质因数分解后算贡献即可.

commment:

无

https://ac.nowcoder.com/acm/contest/5674/E

题意

计算如题描述的累积式子。

题解

枚举x和y的因子，同样的因子，不同的因子没有贡献，放到一起计算。然后被卡了。

comment

还得记忆化x和y的某因子次数，因为贡献是一个关于因子值的一次式，就可以先把前面的系数处理出来。以防那种2*3*5*7*11*13*17的数据。