$$f(x) = \sum_{i=1}^x\prod_{j=1}^ix$$
find $f(N)$mod $25602017$ $(1 \leq N \leq 10^{18})$
N and 25602017 is relative prime
I' calculate that
$$g(N)=\frac{x(x^x-1)}{x-1}$$
I'm use divide and conquer from
$$ g(N)$$
to calculate
$$x^x$$
in $O(log(x))$
Teacher reject my submission
Teacher tell me that invert mod in
$$x(x^x-1)$$
How to do?
To calculate $$x(x^x-1)\mod{25602017}$$
You can calculate $$x\mod{25602017}$$
and $$(x^x-1)\mod{25602017}$$ separately, because $$x(x^x-1) \mod{25602017}=(x\mod{25602017})((x^x-1)\mod{25602017}) $$
,but $$(x^x-1)\mod{25602017} = (x^x+25602016)\mod{25602017}$$
While $x^x$ can be calculated in $\mathcal{O}(\log(x))$ using exponentiation by squaring method.
After calculating $x(x^x-1)\mod{25602017}$, you can calculate $$\frac{x(x^x-1)}{x-1} \mod{25602017}$$ with the modular multiplicative inverse.
