首页 > Gcd Product
开通博客写题解
头像 lifehappy
发表于 2021-02-21 21:49:47
Gcd Product 观察式子，不难发现，二者对于给定的都是可以确定的，跟变量无关， 设，得到， 接下来我们考虑化简。 ，则，可得： 同余方程。 由，则，所以。 由，则，因为，所以有。 所以，分别在膜下有且只有唯一解，有， 可得，要使， 相当于在的基础上给组合分配，凑得。 设，所以解的个数就是，则 展开全文
去ta的博客 赞 (4) 回复(5) 收起
头像 zqy1018_
发表于 2021-05-22 18:58:06
F Gcd Product 题意很短。主要介绍一种和 std 不同、比 std 思维量更低一些的做法。 定义 ，即 是三元组的集合。 定义 ，即两个三元组集合的积为另一个三元组的集合。 那么：通过打表可以发现， 具有积性。即对于互质的 有 。且当 为质数的幂次时，容易直接求出 。 于是只需要按 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”