Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

01/4
19:14
dfs

[bzoj 1053] HAOI2007 反素数ant

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足:g(x)>g(i) 0<i<x,则称x为反质数。例如,整数1,2,4,6等都是反质数。
现在给定一个数N,你能求出不超过N的最大的反质数么?

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

一个数N(1<=N<=2,000,000,000)。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

不超过N的最大的反质数。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

1000

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

840

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

首先要知道一个结论:一个数约数个数=所有素因子的次数+1的乘积 并且这个结论非常地好想(严肃脸),然后会发现这样的话2000000000之内至多用到前11个素数(黄学长说是12个 但的确是11个),然后直接暴搜就可以辣

c++:

加强版:n<=10^100

pascal:

 

[bzoj 1053] HAOI2007 反素数ant