louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共3篇）

题解 | 信息学奥赛一本通樱花

思路先考虑.也就是.考虑..因为互质,所以.所以当且仅当且时满足条件.考虑把质因数分解,每个质因数分给和,或者和,或者全部给.形式化地,,.改成也就是.复杂度.(反正复杂度都这样了还写线性筛干嘛qwq). 代码 #include<bits/stdc++.h> using namespa...

约数质数

2019-09-01

1 528

题解 | 信息学奥赛一本通聪明的燕姿

思路一个数的约数和为(你们都会).很明显约数和肯定大于该数,也就是答案也不会超过.可以先处理出以内的质数,然后DFS构造出所有满足条件的答案.依次枚举每个质数以及该质数的幂,除去,答案就乘.当为或者为质数且大于当前枚举的质数,就计入答案序列.这个复杂度不好证明啊qwq,感觉上限大概是级别的.也不用...

构造约数

2019-08-31

0 680

题解 | 信息学奥赛一本通 X-factor Chain

思路一种简单的构造方法就是将作为最后一个数,之前每个数是后一个数除以任意一个因子,这样构造一定是最优的.因此第一个答案就显而易见了,就是的质因子个数.(这里若,算个质因子)如果不是任何质数的平方的倍数,那么方案就是每次除以的因子的全排列.如果,的排列会有重复,也就是说会重复计算.因此若,第二个答案...

约数

2019-08-31

2 824