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!

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def offset(l, flag):
	x = 0
	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
	ans += offset(temp, True)
	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):
	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
	li = listoffactors(s)
	nps = powersof2[s]
	for i in li:
		nps -= nonPeriodicStrings(i, m)
		nps %= m
	nonperiodics[s] = nps
	return nps
cc = input().split(' ')
a = int(cc[0])
m = int(cc[1])
prime = [True for i in range(a + 1)]
pow2(a, m)
sieve(a + 1)
if prime[a]:
	l = powersof2[a] - 2
	print(l)
else:
	print(nonPeriodicStrings(a, m))


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)
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
	print(res % M)


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)
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)


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)
else:
	res = 2 ** N - 2
	for el in get_factors(N):
		res -= 2 ** el - 2
	print(res % M)


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:
	v = n // v
	ans -= 2 ** v - 2
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)


powers = [0 for i in range(150001)]

def factorize(n):
	factors = set()
	for i in range(1, n):
		if i * i > n:
			break
		elif 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
	for j in done:
		if temp == 1:
			break
		ans = (ans + 2 ** gcd(temp, j) % MOD) % MOD
		temp //= gcd(temp, j)
	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]
	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])


(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))