Indian National Olympiad in Informatics 2015
A string is any nonempty sequence of 0s and 1s. Examples of strings are 00, 101, 111000, 1, 0, 01. The length of a string is the number of symbols in it. For example, the length of 111000 is 6. If u and v are strings, then uv is the string obtained by concatenating u and v. For example if u = 110 and v = 0010 then uv = 1100010.
A string w is periodic if there exists a string v such that w = vn = vv · · · v (n times), for some n ≥ 2. Note that in this case the length of v is strictly less than that of w. For example, 110110 is periodic, because it is vv for v = 110.
Given a positive integer N , find the number of strings of length N which are not periodic. Report the answer modulo M . The non-periodic strings of length 2 are 10 and 01. The non- periodic strings of length 3 are 001, 010, 011, 100, 101, and 110.

-----Input format-----
A single line, with two space-separated integers, N and M .

-----Output format-----
A single integer, the number of non-periodic strings of length N , modulo M .

-----Test Data-----
In all subtasks, 2 ≤ M ≤ 108. The testdata is grouped into 4 subtasks.
Subtask 1 (10 marks) 1 ≤ N ≤ 4000. N is the product of two distinct prime numbers.
Subtask 2 (20 marks) 1 ≤ N ≤ 4000. N is a power of a prime number.
Subtask 3 (35 marks) 1 ≤ N ≤ 4000.
Subtask 4 (35 marks) 1 ≤ N ≤ 150000.

-----Example-----
Here is the sample input and output corresponding to the example above:

-----Sample input-----
3 176

-----Sample output-----
6

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
def offset(l, flag):
    x = 0
    # print(l)
    for i in range(1, len(l)):
        temp = []
        for j in range(i):
            v = getbig(l[i], l[j], fs)
            if v > 1:
                temp.append(v)
                if flag:
                    x += 2**v - 2
                else:
                    x -= 2**v - 2
        x += offset(temp, not flag)
    return x
    
def getbig(v1, v2, factors):
    x = 1
    for f in factors:
        while v1%f == 0 and v2%f == 0:
            v1//=f
            v2//=f
            x*=f
    return x
    
def prime_factors(n):
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return factors
    
n,m = map(int, input().split())
if n == 1:
    print(1)
else:
    fs = prime_factors(n)
    fs.discard(n)
    ans = 2**n-2
    temp = []
    for v in fs:
        v = n//v
        temp.append(v)
        ans -= 2**v - 2
        # print(ans)
    ans += offset(temp, True)
    # print(fs)
    print(ans%m)

from math import sqrt

def per(n):
    if n in diz:
        return diz[n]
    else:
        counter=pow(2,n,m)
        for i in range(1,int(sqrt(n))+1):
            if n%i==0:
                counter-=per(i)
                if i!=1 and i!=(n//i):
                    counter-=per(n//i)
                counter%=m
        return counter
        
n, m = map(int, input().split())
diz={1:2}
print(per(n))
counter=pow(2,n,m)

powersof2 = {}
nonperiodics= {}


def pow2(x, m):
    powersof2[0] = 1%m
    powersof2[1] = 2%m
    for i in range(2, x+1):
        powersof2[i] = (powersof2[i-1]*2)%m


def nonperiodicsfill(x):
    for i in range(x):
        nonperiodics[i]=0


def listoffactors(x):
    lista=[]
    for i in range(1, 1 + x//2):
        if x%i == 0 :
            lista.append(i)
    return lista


def sieve(x):
    for i in range(2, x):
        if prime[i]:
            for q in range(i*2, x, i):
                prime[q] = False


def nonPeriodicStrings(s,m):
   # print("\nNPS"+ str(s) +" "+ str(m) + "\n")
    if s==1:
        return 2%m
    if s in nonperiodics:
        return nonperiodics[s]
    if prime[s]:
        nps = (powersof2[s] - 2) % m
        nonperiodics[s] = nps
        return nps
 #   print(s)
    li = listoffactors(s)
   # print(li)
    nps = powersof2[s]
    for i in li:
        nps -= nonPeriodicStrings(i, m)
    #    print(nonPeriodicStrings(i,m))
        nps %= m
    nonperiodics[s] = nps
    return nps


cc = input().split(' ')
a= int(cc[0])
m= int(cc[1])
#print(a)
#print(m)
prime = [True for i in range(a+1)]
#m = int(input())
pow2(a, m)
#print(powersof2)
sieve(a+1)
#print(prime)
if prime[a]:
    l = powersof2[a] - 2
    print(l)
else:
    print(nonPeriodicStrings(a, m))





# cook your dish here
import sys


def get_factor(n:int):
    for i in range(2, int(n**0.5)+1):
        if(n%i==0):
            return i, n
    return n,n

N,M=sys.stdin.readline().strip().split(" ")[:2]

N,M=int(N),int(M)
if(N in (0,1)): print(0)
#elif(N==1): print(2%M)
else:
    res=2**N-2
    f_, n_=get_factor(N)
    if(f_<N):
        res_=[f_]
        res-=2**(N//f_)-2
        while(f_<n_):
            f_, n_=get_factor(n_//f_)
            if(f_ not in res_):
               res_.append(f_)
               res-=2**(N//f_)-2
        if(n_ not in res_):
            res-=2**(N//n_)-2
#        if(N%(f_**2)==0):
#            res-=2**(N//f_)-2
#        else:
#            res-=2**(N//f_)-2+2**f_-2
    print(res%M)
    
        

# cook your dish here
import sys


def get_factor(n:int):
    for i in range(2, int(n**0.5)+1):
        if(n%i==0):
            return i
            

N,M=sys.stdin.readline().strip().split(" ")[:2]

N,M=int(N),int(M)
if(N in (0,1)): print(0)
#elif(N==1): print(2%M)
else:
    res=2**N-2
    f_=get_factor(N)
    if(f_):
        if(N%(f_**2)==0):
            res-=2**(N//f_)-2
        else:
            res-=2**(N//f_)-2+2**f_-2
            
    print(res%M)
    
        

# cook your dish here
import sys

def get_factors(n:int):
    for i in range(2, n//2+1):
        if(n%i==0):
            yield i

N,M=sys.stdin.readline().strip().split(" ")[:2]

N,M=int(N),int(M)
if(N in (0,1)): print(0)
#elif(N==1): print(2%M)
else:
    res=2**N-2
    for el in get_factors(N):
        res-=2**el-2
    print(res%M)
    
        

# cook your dish here
def offset(l, flag):
    x = 0
    # print(l)
    for i in range(1, len(l)):
        temp = []
        for j in range(i):
            v = getbig(l[i], l[j], fs)
            if v > 1:
                temp.append(v)
                if flag:
                    x += 2**v - 2
                else:
                    x -= 2**v - 2
        x += offset(temp, not flag)
    return x
    
def getbig(v1, v2, factors):
    x = 1
    for f in factors:
        while v1%f == 0 and v2%f == 0:
            v1//=f
            v2//=f
            x*=f
    return x
    
def prime_factors(n):
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return factors
    
n,m = map(int, input().split())
if n == 1:
    print(1)
else:
    fs = prime_factors(n)
    fs.discard(n)
    ans = 2**n-2
    temp = []
    for v in fs:
        v = n//v
        temp.append(v)
        ans -= 2**v - 2
        # print(ans)
    ans += offset(temp, True)
    # print(fs)
    print(ans%m)

# cook your dish here
def prime_factors(n):
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return factors
    
n,m = map(int, input().split())
fs = prime_factors(n)
fs.discard(n)
ans = 2**n-2
for v in fs:
    # print(ans, v)
    v = n//v
    # print(v)
    ans -= 2**v - 2
    # print(ans)
# print(fs)
print(ans%m)

# cook your dish here
def prime_factors(n):
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(n)
            if n % i != 0:
                factors.add(i)
            break
            
    return factors
    
n,m = map(int, input().split())
if n > 1:
    fs = prime_factors(n)
    ans = 2**n-2
    for v in fs:
        # print(ans, v)
        ans -= 2**v - 2
        # print(ans)
    # print(fs)
    print(ans%m)
else:
    print(1)

# cook your dish here
def prime_factors(n):
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(n)
            if n % i != 0:
                factors.add(i)
            break
            
    return factors
    
n,m = map(int, input().split())
fs = prime_factors(n)
ans = 2**n-2
for v in fs:
    if v != n:
        # print(ans, v)
        ans -= 2**v - 2
        # print(ans)
# print(fs)
print(ans%m)

# cook your dish here
def prime_factors(n):
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
            factors.add(n)
            break
            
    return factors
    
n,m = map(int, input().split())
fs = prime_factors(n)
ans = 2**n-2
for v in fs:
    if v != n:
        # print(ans, v)
        ans -= 2**v - 2
        # print(ans)
# print(fs)
print(ans%m)

# cook your dish here
def prime_factors(n):
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return factors
    
n,m = map(int, input().split())
fs = prime_factors(n)
ans = 2**n-2
for v in fs:
    if v != n:
        ans -= 2**v - 2
# print(fs)
print(ans%m)

def mod(f,m):
    if f==1:
        return(2%m)
    elif f%2==0:
        return(((mod(f//2,m))**2)%m)
    else:
        return((((mod(f//2,m))**2)*2)%m)
n,m=list(map(int,input().strip().split()))
l=[0 for i in range(n+1)]
l[0],l[1]=1,1
for i in range(2,n+1):
    if l[i]==0:
        t=2
        while t*i<=n:
            l[t*i]=1
            t+=1
prime=[]
for i in range(len(l)):
    if l[i]==0:
        prime.append(i)
t=0
for j in prime:
    if n%j==0:
        t+=mod(n//j,m)
s=mod(n,m)
t%=m
if s-t>0:
    print(s-t)
else:
    print(m-s+t)

        

import random
def miller_rabin(n, k):

    if n == 2 or n==3:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
pows = {1:2}
n, k = list(map(int, input().split(' ')))
T = pow(2,n)
if miller_rabin(n,6):
    print((T-2)%k)
else:
    m = 0
    for i in range(2,n//2+1):
        if n%i==0:
            if i>50000:
                a = 6
            elif i>20000:
                a = 5
            else:
                a = 4
            if miller_rabin(i,a):
                pows[i]=pow(2,i)-2
                m+=pows[i]
            else:
                w = 0
                for j in pows:
                    if i%j==0:
                        w+=pows[j]
                    if j>i//2:
                        break
                pows[i] = pow(2,i)-w
                m+=pows[i]

    print((T-m-2)%k)


# cook your dish here
import random
def miller_rabin(n, k):

    if n == 2 or n==3:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
pows = {1:2}
n, k = list(map(int, input().split(' ')))
T = pow(2,n)
if miller_rabin(n,6):
    print((T-2)%k)
else:
    m = 0
    for i in range(2,n//2+1):
        if n%i==0:
            if i>50000:
                a = 6
            elif i>20000:
                a = 5
            else:
                a = 4
            if miller_rabin(i,a):
                pows[i]=pow(2,i)-2
                m+=pows[i]
            else:
                w = 0
                for j in pows:
                    if i%j==0:
                        w+=pows[j]
                    if j>i//2:
                        break
                pows[i] = pow(2,i)-w
                m+=pows[i]

    print((T-m-2)%k)



powers=[0 for i in range(150001)]

def factorize(n):
    factors=set()
    for i in range(1,n):
        if i*i>n:
            break
        else:
            if (n%i)==0:
                factors.add(i)
                factors.add(n//i)
    factors.remove(n)
    return factors

def calc(m):
    powers[0]=1
    for i in range(1,150001):
        powers[i]=(powers[i-1]*2)%m

n,m=list(map(int,input().split()))
calc(m)
dp=[0 for i in range(n+1)]
dp[1]=2
for i in range(2,n+1):
    factors=factorize(i)
    dp[i]=powers[i]
    for num in factors:
        dp[i]-=dp[num]
        dp[i]=(dp[i]+m)%m
print(dp[n])



n, m = map(int, input().split())
p, mem = 3, []
res = 2**n - 2
if n % 2 == 0:
    res -= 2
while p < n:
    if not any(p % e == 0 for e in mem) and n % p == 0 :
        mem.append(p)
        res -= 2**p - 2
        
    p +=2
        
print(res % m)
            
            
        
        
        
        
        

from math import sqrt, gcd
n, MOD = list(map(int, input().split()))
factors = set()
for i in range(2, 1+int(sqrt(n))):
    if(n % i == 0):
        factors.add(i)
        factors.add(n//i)
factors = sorted(list(factors), reverse = True)
ans = 2**n
if(factors == []):
    ans -= 2
done = []
for i in factors:
    ans -= (2**i) % MOD
    temp = i
    #print("i=",i,ans)
    for j in done:
        if(temp == 1):
            break
        ans = (ans + (2**gcd(temp,j))%MOD) % MOD
        temp //= gcd(temp,j)
        #print("j=",j,ans)
    done.append(i)
if(factors):
    ans -= max(0,len(factors)//2 - 1) * 2
print(ans%MOD)


N,M = map(int,input().split())
dp = [0]*( (2*(10**5)) +1)
power = [0]*( (2*(10**5)) +1)
power[1] = 2
dp[1] = 2%int(M)
for i in range(2,int(N)+1):
    power[i] = (2*power[i-1])%int(M)


for i in range(2,int(N)+1):
    if(int(N)%i!=0):
        continue

    dp[i] = power[i]
    #print(power[i])
    for j in range(1,int(int(i)/2)+1):
        if(i%j==0):
            dp[i] = dp[i]-dp[j]
            if(dp[i]<0):
                dp[i] += int(M)
        
print(dp[int(N)]) 

factors = []

def fact(n):
    factors.clear()
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            factors.append(i)
            if i*i != n:
                factors.append(n//i)
n , m  = map(int,input().split())

dp = [0]*( (2*(10**5)) +1)

dp[2] = 2%m
dp[3] = 6%m
dp[4] = 12%m

if n > 4:
    for i in range(5,n+1):
        fact(i)
        k = (pow(2,i,m) - 2)%m
        if len(factors) == 0:
            dp[i] = k
        else:
            sub = 0
            for j in factors:
                sub += dp[j]
                sub %= m
            dp[i] = (k - sub)%m
print(dp[n])


# cook your dish here

N, M  =  map(int, input().split())

pow2ModM = [1 for i in range(N + 1)]
pow2ModM[0] = 1
for i in range(1, N + 1):
  pow2ModM[i] = (pow2ModM[i - 1] * 2) % M

def fModM(N):
  answer = pow2ModM[N]
  for d in range(1, N):
    if N % d == 0:
      answer = (answer - fModM(d)) % M
  return answer

print(fModM(N))