钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

文远知行杯E题枚举求和题解

题面

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

解题

首先研究 k|gcd(i, j) . 很显然, 如果该式成立, 那么 k 必然是 i, j 的公因子, 也就是说 i, j 都是 k 的倍数.
所以我们所求的就是符合要求的数对的个数, 根据数学知识 1 ~ n 中有 a = n / kk 的倍数, 1 ~ m 中有 b = m / kk 的倍数, 符合要求的数对个数就是 a * b .

踩的坑

别问, 问就是不开long long见祖宗.

完整AC代码