p294.ans2
======================
6

=================
p294.in1
======================
3

=================
p294.ans1
======================
4

=================
p294.in2
======================
4

=================
statement.txt
======================
294. He's Circles
time limit per test: 1.75 sec.
memory limit per test: 65536 KB
input: standard
output: standard



He wrote n letters "X" and "E" in a circle. He thought that there were 2n possibilities to do it, because each letter may be either "X" or "E". But Qc noticed that some different sequences of letters can be transformed one to another with a circular shift (thus representing actually the same circular string).
For example, strings "XXE"-"XEX"-"EXX" are actually the same.
Qc wants to know how many different circular strings of n letters exist. Help him to find that out.


Input
The input file contains a single integer 1 <= n <= 200000.

Output
Output a single integer --- the number circular strings of length n.

Sample test(s)

Input
Test #1
3

Test #2
4

Output
Test #1
4

Test #2
6
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

=================
p294.py
======================
"""
This is the classical example of the Burnside lemma. There are
many tutorials online, as well as the Wiki page, that go through 
the full idea, but roughly we count the number of fixed points for
every individual "view", which ensures that in every equivalent class,
the "total count" is the same and equal to the number of possible transformations.
This is the non-formal and somewhat vague explanation, where more details can be 
found in https://cp-algorithms.com/combinatorics/burnside.html, as well as 
solution to this particular problem.

In this problem, the transformations are the cyclic shifts, and a way of counting the
number of fixed points is by iterating through the cyclic shift "i" (1 to N), and counting
how many binary strings are a fixed point under this. This is a simple combinatorics problem
as essentially we know that 1, 1 + i, 1 + 2i, ... are all the same, or we will have gcd(N, i)
such groups which we can choose independently. In other words, the final answer is:

(SUM 2^gcd(N, i)) / N

In this problem N is fairly large, but we can notice that gcd(N, i) can take O(sqrt(N)) values
(technically even less as it's the number of divisors which is closer to O(N^1/3)), so we only
need to calculate 2^K a few times. 

Main reason we implement this in Python instead of C++ is because it requires BigInteger.
"""
import math
import sys

sys.set_int_max_str_digits(1000000)


def fast_pow(p, k):
    r = 1
    while k:
        if k & 1:
            r *= p
        k >>= 1
        p *= p

    return r


def main():
    n = int(input())

    cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        cnt[math.gcd(n, i)] += 1

    ans = 0
    for v in range(1, n + 1):
        if cnt[v] == 0:
            continue
        ans += cnt[v] * fast_pow(2, v)

    ans //= n
    print(ans)


if __name__ == "__main__":
    main()

=================
