# 题目

Problem 555: McCarthy 91 function

The McCarthy 91 function is defined as follows:

We can generalize this definition by abstracting away the constants into new variables:

This way, we have $M_{91}=M_{100,11,10}$.
Let $F_{m,k,s}$ be the set of fixed points of $M_{m,k,s}$. That is,
$F_{m,k,s}=\{n\in\mathbb{N}|M_{m,k,s}(n)=n\}$
For example, the only fixed point of $M_{91}$ is $n=91$. In other words, $F_{100,11,10}=\{91\}$.
Now, define $SF(m,k,s)$ as the sum of the elements in $F_{m,k,s}$ and let $S(p,m)=\sum_{1\le s.

For example, $S(10,10)=225$ and $S(1000,1000)=208724467$.
Find $S(10^6,10^6)$.

# 分析

$M_{m,k,s}(n)$ 的几个典型值进行简单计算后，我们发现， 对于正整数 $b,c$， 当且仅当 $k=b(c+1),s=bc,(1\le{s} 时，
$F_{m,k,s}=\{m-bc+i|1\le{i}\le{b}\}$.

$SF(m,k,s)=bm+\frac{b(b+1)}{2}-b^2c$.

$\sum_{c=1}^{a}SF(m,k,s)=\frac{(1+2m-ab)ab}{2}$.

# 解答

main = let p = 10^6; m = p in print $(flip div 2)$ sum \$
takeWhile (>0) [(1+2*m-z)*z | b <- [1..], let z = b * (div p b - 1)]


• div p b - 1 就是上面的分析中提到的 a
• z 就是 ab