当前位置:首页 > 数学 > 正文
SSOJ2905反素数Antiprime[一本通][POI2001]
1103+

题目大意:不超过n的最大反素数是多少?所谓反素数,就是(自己以内)约数个数最多的数字。

题目描述

原题来自:POI 2001

如果一个大于等于 1 的正整数 n,满足所有小于 n 且大于等于 1 的所有正整数的约数个数都小于 n 的约数个数,则 n 是一个反素数。譬如:1,2,4,6,12,24,它们都是反素数。

请你计算不大于 n 的最大反素数。

输入

一行一个正整数 n

输出

只包含一个整数,即不大于 n 的最大反素数。

提示

样例输入

1000

样例输出

840

对于 10% 的数据,1n103

对于 40% 的数据,1n106

对于 100% 的数据,1n2×109

解题思路

暴力枚举每个质因子的次幂,这个数不能超过n,而且是反素数。

显然,我们会尽量选择小的质因子,因为如果质因子小,可以多乘几个,约数更多;另外,我们也希望质因子种类多一点,因为约数个数等于各个质因子次幂加1相乘。

基于这个原则,我们会发现,这个数的质因子肯定都是从小打到开始选择的,当第一个质因子次幂比较高的时候,就可以选下一个质因子,而且不会跳着选,因为如果选择一个更大的质因子,总可以将这个质因子换成小的,从而实现约数个数一样但数字更小。

结论:质因子从小到大连续,且后面的质因子次幂不超过前面的!因为超过的话,可以交换一下,约数个数一样且更小。

最后爆搜的时候,确定每个质因子的范围即可,如果乘积超过n结束递归。

程序实现

SSOJ2905反素数Antiprime[一本通][POI2001]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!