Project Euler Problem 850
Any positive real number x can be decomposed into integer and fractional parts lfloor x rfloor + x, where lfloor x rfloo
Solution
Answer: 878255725
Let
$$f_k(n)=\sum_{i=1}^n \left{\frac{i^k}{n}\right}.$$
For odd $k$, pairing $i$ with $n-i$ gives
$$i^k+(n-i)^k\equiv 0 \pmod n,$$
so the corresponding fractional parts add to $1$, unless $n\mid i^k$, in which case both are $0$.
Hence
$$f_k(n)=\frac{n-r_k(n)}2,$$
where
$$r_k(n)=#{1\le i\le n:\ n\mid i^k}.$$
If
$$n=\prod p^{a_p},$$
then
$$n\mid i^k \iff v_p(i)\ge \left\lceil \frac{a_p}{k}\right\rceil$$
for every prime $p$, so
$$r_k(n)=\prod_p p^{,a_p-\lceil a_p/k\rceil }.$$
Therefore
$$S(N) = \frac12 \sum_{\substack{k\le N\k\text{ odd}}} \left( \sum_{n\le N} n - \sum_{n\le N} r_k(n) \right).$$
Using multiplicativity together with the Dirichlet–series decomposition of $r_k$, one can reduce the computation to finitely many divisor sums (only $k\le 45$ contribute nontrivially because $2^{46}>33557799775533$). Evaluating the resulting sums exactly modulo $977676779$ gives the required value.
Answer: 84664213