Koptanovia's blog

By Koptanovia, history, 3 months ago, In English,

http://codeforces.com/gym/101727/problem/D

I tried simulating the problem statement to recognize any sort of pattern, but ran out of memory on very small input.

any hint would be greatly appreciated!

UPDATE: Accepted, answer = phi(n) https://en.wikipedia.org/wiki/Euler%27s_totient_function

 
 
 
 
  • Vote: I like it  
  • +14
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Koptanovia (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How did you calculate phi(n) for n ~ 1e13?
Can you please explain it a bit?