HDU 6063 RXD and math

原题连接 http://acm.hdu.edu.cn/showproblem.php?pid=6063

题目的意思是要求计算：

∑i=1nkμ2(i)⌊nki‾‾‾√⌋

直接计算显得有点力不从心。

这个式子可以通过逻辑推理得出。

∑i=1Sμ2(i)⌊Si‾‾√⌋=S

建立一种映射。

对于n的质因数分解形式：

n=∏i=1rPaii

指数为偶数和奇数时区分对待。

当某个素因子指数为奇数时。我们提出一个这个素数。

我们记被提出的素因子组成的集合为 b(b是一个数字)

剩余的素因子组成的集合为 a2(这是因为，剩余素因子个数都是偶数)

这时候有：

n=a2b，a,b>0

且此时。 a 最大。

这里最大的意思是说。对于任意正整数n

我们将其改写成 n=a2b 的形式

则 a 是所有形式中最大的那个。

如果用有序对(a,b)表示 a2b

那么每一个正整数 n 都有且只对应一个有序对(a,b) ，有且只对应一个 b

其中μ(b)!=0

那么对于 n∈[1,S] 中， b 所对应的n的数量为：

μ2(b)⌊Sb‾‾√⌋

当 b 含有两个相同素因子时，那么a必然不是最大。

这里莫比乌斯函数更像是一种真值表达式。

[b中不含有两个以上相同素因子]=μ2(b)

因为 n 只对应一个b,且 b<=n

所以：

∑i=1Sμ2(i)⌊Si‾‾√⌋=S

answer=nk