my idea:

 sum( (-1)^m *  a^(n/(p[k1]*p[k2]*..*p[km] ) ) ), where p[i] - is prime number and n % p[i] == 0.

also WA(4) why?
1. Q[k]-number for which k- minimal period
2 Q[k]=a^k-sum(Q[i],i<k k%i==0)
3. answer =Q[n]/n

AC has. Big numbers rules from Test4.
Learhed Python and taken Ac quickly
Much more comfortable than java


Edited by author 12.02.2018 11:13

There are __int128 and libquadmath with __float128 in GCC/clang. I sure there are problems, where these are sufficient to get AC. What do you think?

[svr] solution (double for by K and I) with optimized long arithmetic by 10^9 base (9 digits packed in one int) in C++ can pass only by compiler choosing (got TLE 49 on Visual Studio and only g++ got AC), but solution uses 0.375 time and 63 Mb of memory - i.e. it is almost NOT a solution :))

So I can't imagine how to pass this on Python, which MUST be too slower than C++.

Edited by author 30.12.2023 14:03