Problem:


Score : 600 points

Problem Statement

Given is a positive integer N.

We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.

Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.

In how many choices of K will N become 1 in the end?

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of choices of K in which N becomes 1 in the end.

Sample Input 1

6

Sample Output 1

3

There are three choices of K in which N becomes 1 in the end: 2, 5, and 6.

In each of these choices, N will change as follows:

When K=2: 6 \to 3 \to 1

When K=5: 6 \to 1

When K=6: 6 \to 1

Sample Input 2

3141

Sample Output 2

13

Sample Input 3

314159265358

Sample Output 3

9



Sample input:
6


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

def divisior(n):

    a = []
    i = 1

    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i == n): continue
            a.append(int(n/i))
        i += 1

    return a

ans = 0
a = divisior(n)

for x in a:
    if x == 1: continue
    tmp = n
    while (tmp%x == 0): tmp /= x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
N_ = copy.deepcopy(N)
count = 0
for K in range(2, N + 1):
    N = N_
    while K <= N:
        if N % K == 0:
            N = N / K
        else:
            N = N - K
    if N == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


def is_k_ok(k, n):
    judge = False
    n_mod_k = n % k
    
    if n_mod_k == 1:
        return True
    
    elif n_mod_k == 0:
        while n % k == 0:
            n = n // k
            
        if n % k == 1:
            return True
        
    return judge 


print(len([k for k in range(2, n+1) if is_k_ok(k, n)]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


def check(n, k):
    while n % k == 0:
        n = n // k
    if n >= k:
        n = n - k * (n // k)
    return n


def count(n):
    total = 0
    cands = set([n, n-1])
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cands.add(i)
            cands.add(n // i)
    for i in range(2, int(n ** 0.5) + 1):
        if (n-1) % i == 0:
            cands.add(i)
            cands.add((n - 1) // i)
    for k in cands:
        if check(n, k) == 1:
            total += 1
    return total


print(count(n))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = []
for k in range(n, 1, -1):
    N = n
    while N >= k:
        if N % k == 1 or N / k == 1 or N - (N % k) == 1:
            a.append(k)
            break
        elif N % k == 0:
            N = N / k
        else:
            break

# print(a)
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 0


def factorize(n):
    fct = []
    for i in range(1, n):
        if n % (i + 1) == 0:
            fct.append(i + 1)
    return fct


def check(num, mod):
    if num % mod == 1:
        return 1
    elif num % mod == 0:
        num = num / mod
        return check(num, mod)
    else:
        return 0


nfct = factorize(n)
n_1fct = factorize(n - 1)

ans += len(n_1fct)
for mod in nfct:
  ans += check(n,mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def tester(n, k):
    temp = n
    while temp % k == 0:
        temp /= k

    if temp % k == 1:
        return True
    else:
        return False

answer= []

for i in range(2, N + 1):
    if tester(N, i):
        answer.append(i)

print(len(answer))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c = 1
num = 2
while num < n:
    ele = num
    num2 = n
    while num2 >= 2:
        if num2 / ele == 1:
            c += 1
            break
        elif num2 - ele == 1:
            c += 1
            break
        else:
            if num2 % ele == 0:
                num2 = num2/ele
            else:
                num2 = num2 - ele
    num += 1
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

count = 0

for k in range(2, n+1):
    if n % k == 0:
        n_new = n // k
        while n_new % k == 0:
            n_new = n_new // k
        if n_new % k == 1:
            count += 1
    else:
        if n % k == 1:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

divisor = [N]
ans = 0

#Nの約数の列挙
for i in range(2,N+1,1):
    if i*i <= N:
        if N % i == 0:
            divisor.append(i)
            divisor.append(N//i)
    else:
        break

#N-1の約数の列挙
yakusuuu = [N-1]
for i in range(2,N,1):
    if i*i <= N:
        if N % i == 1:
            yakusuuu.append(i)
            yakusuuu.append((N-1)//i)

for i in yakusuuu:
    if N % i == 1:
        ans += 1

#print(divisor)
#print(yakusuuu)

n=N

for K in divisor:
    #print(K)
    for i in range(N):
        if n % K == 0:
            n = n//K#ここで全部N==1になっちゃう
        else:
            break
    

    if N == 1:
        ans += 1
        
    else:
        n %= K
        if n == 1:
            ans += 1 
    n =N
    
        




print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)



ret = 0
a = make_divisors(n)
for k in a:
    if k == 1:
        continue
    m = n
    while m >= k:
        if m % k == 0:
            m //= k
        else:
            m -= k
    if m == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)



ret = 0
for k in make_divisors(n):
    if k == 1:
        continue
    m = n
    while m >= k:
        if m % k == 0:
            m //= k
        else:
            m -= k
    if m == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
count=0
list2=[]
for i in range(1,N+1) :
  if (N-1)%i==0 :
    if float((N-1)/i)>float(i) :
      if float(i)==float(1) :
      	list2.append(N-1)
      else :
        list2.append(i)
        list2.append(int(((N-1)/i)))
      
    elif float((N-1)/i)==float(i) and i!=1 :
      list2.append(i)
      
    else :
      
      break

count=len(list2)


list1=[]
for i in range(1,N+1) :
  if N%i==0 :
    if float(N/i)>float(i) :
      if float(i)==float(1) :
      	list1.append(N)
      else :
        list1.append(i)
        list1.append(int((N/i)))
      
    elif float(N/i)==float(i) and i!=1 :
      list1.append(i)
      
    else :
      
      break


for youso in list1 :
  
  if N%youso==0 :
    n1=N
    while (n1%youso==0) :
      n1=n1/youso
    if n1%youso==1 :
      count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def sousa(n1,k) :
  n=n1
  while(n>1) :
    if n%k==0 :
      n=n/k
    else :
      n-=k
  if n==1 :
    return True
  else :
    return False
  
N=int(input())
count=0
for i in range(2,N+1):
  if sousa(N,i) :
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors
ans = make_divisors(N-1)
del ans[0]
cand = make_divisors(N)
del cand[0]
for one in cand:
    n = N
    while True:
        if n%one==0:
            n = N//one
        else:
            if n%one==1:
                ans.append(one)
            break
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
def calc_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def div_or_sub(n, k):
    while k <= n:
        if n % k == 0:
            n //= k
        else:
            n -= k
    return n

n = int(input())
cnt = len(calc_divisors(n - 1)) - 1
n_divisors = calc_divisors(n)
for divisor in n_divisors[1:]:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
  def make_divisors(n):
      divisors = []
      for i in range(1, int(n**0.5)+1):
          if n % i == 0:
              divisors.append(i)
              if i != n // i:
                  divisors.append(n//i)
      divisors.sort()
      return divisors

  n = int(input())
  l = make_divisors(n)
  ans = make_divisors(n-1)
  for i in l:
    m=n
    if i==1:
      continue
    else:
      while(m%i==0):
        m//=i
    if m==1:
      ans.append(i)
    else:
      if i in make_divisors(m-1):
        ans.append(i)
  ans=set(ans)
  print(len(ans)-1)  

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def gen(x):
    root = int(pow(x, 0.5))

    yield x

    for k in range(2, root):
        if x % k == 0:
            yield k
            yield x // k

    if x % root == 0:
        yield root
        if root != x // root:
            yield x // root


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

    # N%K!=0
    cnt = sum(1 for _ in gen(N - 1))

    # N%K==0
    for k in gen(N):
        x = N
        while x % k == 0:
            x //= k

        if x % k == 1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gen(x):
    root = int(pow(x, 0.5))

    yield x

    for k in range(2, root):
        if x % k == 0:
            yield k
            yield x // k

    if x % root == 0:
        yield root
        if root != x // root:
            yield x // root


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

    # N%K!=0
    cnt = len(tuple(gen(N - 1)))

    # N%K==0
    for k in gen(N):
        x = N
        while x % k == 0:
            x //= k

        if x % k == 1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gen(x):
    root = int(pow(x, 0.5))

    yield x

    for k in range(2, root):
        if x % k == 0:
            yield k
            yield x // k

    if x % root == 0:
        yield root
        if root * root != x:
            yield x // root


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

    # N%K!=0
    cnt = len(tuple(gen(N - 1)))

    # N%K==0
    for k in gen(N):
        x = N
        while x % k == 0:
            x //= k

        if x % k == 1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gen(x):
    root = int(pow(x, 0.5))

    yield x

    for k in range(2, root):
        if x % k == 0:
            yield k
            yield x // k

    k = root
    if x % k == 0:
        yield k
        if k * k != x:
            yield x // k


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

    # N%K!=0
    cnt = len(tuple(gen(N - 1)))

    # N%K==0
    for k in gen(N):
        X = N
        while X % k == 0:
            X //= k
        cnt += (X % k == 1)

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gen(x):
    root = int(pow(x, 0.5))

    yield x

    for k in range(2, root):
        if x % k == 0:
            yield k
            yield x // k

    k = root
    if x % k == 0:
        yield k
        if k * k != x:
            yield x // k


N = int(input())

# N%K!=0
cnt = len(tuple(gen(N - 1)))

# N%K==0
for k in gen(N):
    X = N
    while X % k == 0:
        X //= k
    cnt += (X % k == 1)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

n = int(input())
ans = set()

for x in make_divisors(n-1):
    ans.add(x)

for x in make_divisors(n):
    m = n
    while m % x == 0:
        m = m//x
    
    for y in sorted(make_divisors(m-1)):
        if y != m-1:
            ans.add(y)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
n = N
ct = 0
for K in range(2,N+1):
    N = n
    while True:
        if N == 1:
            ct += 1
            break
        elif N < K:
            break
        if N%K==0:
            N = int(N/K)
        else:
            N = N-K
print(ct)

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**9)

N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

ds = set(make_divisors(N)) | set(make_divisors(N-1))

def check(n,k):
    if n<k:
        return n==1
    elif n%k==0:
        return check(n//k,k)
    else:
        return check(n-k,k)

ds.remove(1)
cnt = 0
for d in ds:
    # print(d)
    if check(N,d):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    if cnt == 2: t = 1
    else: t = 2
    for i in range(cnt, last + 1, t):
      if x % i == 0:
        x //= i
        p[i] = 1
        if cnt == 2: cnt = 3
        else: cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N = int(input())

P = prime(N - 1)

if N == 2:
  print(1)
  exit()

ans = 1
for i in P.keys():
  ans *= P[i] + 1
ans -= 1

P = prime(N)
D = [1]
for i in P.keys():
  L = len(D)
  n = i
  for j in range(P[i]):
    for k in range(L):
      D.append(D[k] * n)
    n *= i


for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def operation(n, k):
    if n%k==0:
        return n/k
    else:
        return n-k
cnt = 0
for k in range(2,N+1):
    x = N
    while x>=k:
        x = operation(x,k)
    if x == 1:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-*-

from sys import stdin


def make_divisors(n):
    divs = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divs.append(i)
            if i != n // i:
                divs.append(n // i)
    return divs


def is_seikou(N, k):
    if k == 1:
        return True
    while N >= k:
        if N % k == 0:
            N /= k
        else:
            N = N - k

        if N == 1:
            return True
    return False


def main():
    N = int(stdin.readline())
    cnt = 0
    divs = list(make_divisors(N)) + list(make_divisors(N - 1))
    divs = list(set(divs))
    divs.sort()
    for i in divs[1:]:
        if is_seikou(N, i):
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
count = 0

for k in range(2, N+1):
    tmpN = N
    while(tmpN >= k):
        if tmpN % k == 0:
            tmpN = tmpN / k
        else:
            tmpN = tmpN - k
    if tmpN == 1:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(i)
    return ans

def check(K,N):
    while 1:
        if N%K == 0:
            N = N//K
        else:
            break
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
    for i in range(len(ans)):
        ans.append(N//ans[i])
    ans = list(set(ans))
    return ans

def check(K,N):
    while 1:
        if N%K == 0:
            N = N//K
        else:
            break
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
    for i in range(len(ans)):
        ans.append(N//ans[i])
    ans = list(set(sorted(ans)))
    return ans

def check(K,N):
    while 1:
        if N%K == 0:
            N = N//K
        else:
            break
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
N=[n]
import collections
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0 and i!=1:
      divisors.append(i)
      if i != n // i and n//i!=1:
        divisors.append(n//i)
  return divisors+[n]
t=make_divisors(n)+make_divisors(n-1)
ans=0
for k in t:
  n=N[0]
  while n>=k:
    if n%k==0:
      n//=k
    else:
      n-=k
  if n==1:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
for i in range(1,math.floor(n**0.5)+1):
    x=n
    if n%i==0:
        while x%i==0:
            x//=i   
        if (x-1)%i==0:
            cnt+=1
        if (i-1)%(n//i)==0:
            cnt+=1

print(ans-2+cnt)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def main():
    n = int(input())
    ans = 0
    div = make_divisors(n)
    for i in div[::1]:
        var = n
        while not var%i:
            var = var // i
        if var%i == 1:
            ans += 1
    ans += len(make_divisors(n-1)) - 1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

L = len(make_divisors(N))

ans = 0
for i in range(1,L):
    t = N
    while t%(make_divisors(N)[i]) == 0:
        t = t//make_divisors(N)[i]
    if t%make_divisors(N)[i] == 1:
        ans = ans + 1
        
print(ans + len(make_divisors(N-1)) -1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def traverse(n,K):
  if n == 1:
    return True
  elif n < K:
    return False
  else:
    if n%K == 0:
      return traverse(n/K,K)
    else:
      return traverse(n%K,K)

count = 0
for i in range(2,N+1):
#  print(i)
  if traverse(N,i):
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
def countfact(n,rem):
    if n!=1:
        for i in range(2,int(math.sqrt(n))+2):
            if n%i==0:
                a,b=n//i,i
                #print(a,'fac1',b,'fac2')
                if a!=1:
                    rem.add(a)
                if b!=1:
                    rem.add(b)
def getfact(n):
    ans=[]
    for i in range(2,int(math.sqrt(n))+2):
        if n%i==0:
            a,b=n//i,i
            ans.append(a)
            ans.append(b)
    ans.sort()
    return ans
n=int(sys.stdin.readline())
count=0
temp=n
rem=set()
rem.add(n-1)
vis=defaultdict(int)
countfact(n-1,rem)
for i in rem:
    vis[i]=1

vis[1]=1
l=getfact(n)
temp=n
m=len(l)
for i in range(m):
    while n%l[i]==0:
        n=n//l[i]
    if n%l[i]==1 and vis[l[i]]==0:
        #print(l[i])
        vis[l[i]]=1
        count+=1
    n=temp
'''for i in range(2,int(math.sqrt(n))+2):
    if n%i==0:
        a,b=n//i,i
        c=0
        if b>a and vis[a]==0:
            vis[a]=1
            while a%1==0 and b>a:
                
                #print(a,'before')
                if b%a==1:
                    c+=1
                a=math.sqrt(a)
                #print(a,'a')
        elif vis[b]==0:
            vis[b]=1
            while b%1==0 and a>b:
                #print(b,'before')
               
                if a%b==1:
                    c+=1
                b=math.sqrt(b)
                #vis[b]=1
                #print(b,'after')
        count+=c
        #countfact(b-1,rem)'''

#print(count,'count')       
ans=len(rem)+count
if 1 in rem:
    ans-=1
#print(rem,'rem')
#print(ans,'ans')
count,z=1,True
while z:
    a=math.sqrt(n)
    #print(a,'a')
    if a%1==0 and vis[a]==0:
        count+=1
    else:
        z=False
    n=a
print(ans+count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    def make_divisors(n):
        divisors = set()
        divisors.add(n)
        divisors.add(n-1)
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                if i != n // i:
                    divisors.add(n//i)
        n = n-1
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                if i != n // i:
                    divisors.add(n//i)
        return divisors

    N = int(input())
    ans = 0
    for K in make_divisors(N):
        tmp = N
        while K <= tmp:
            if tmp%K == 0:
                tmp //= K
            else:
                tmp %= K
        if tmp == 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MAX_PRIME = 10**5
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor

n = int(input())
ans = 1
for _, c in factorization(n-1).items():
    ans *= c + 1

f = factorization(n)
k = list(f.keys())
def dfs(num, i, cum, searched):
    if num not in searched:
        x = n
        while x % num == 0 and x > 0:
            x //= num
        if x % num == 1:
            cum += 1
    searched.add(num)
    if i < len(k):
        p = k[i]
        for j in range(f[p]+1):
            cum = dfs(num * p ** j, i+1, cum, searched)
    return cum

print(f)
print(dfs(1, 0, 0, set()) + ans - 1, ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
def countfact(n,rem):
    if n!=1:
        for i in range(2,int(math.sqrt(n))+2):
            if n%i==0:
                a,b=n//i,i
                #print(a,'fac1',b,'fac2')
                if a!=1:
                    rem.add(a)
                if b!=1:
                    rem.add(b)
def getfact(n):
    ans=[]
    for i in range(2,int(math.sqrt(n))+2):
        if n%i==0:
            a,b=n//i,i
            ans.append(a)
            ans.append(b)
    ans.sort()
    return ans
n=int(sys.stdin.readline())
count=0
temp=n
rem=set()
rem.add(n-1)
vis=defaultdict(int)
countfact(n-1,rem)
for i in rem:
    vis[i]=1

vis[1]=1
l=getfact(n)
temp=n
for i in range(len(l)):
    while n%l[i]==0:
        n=n//l[i]
    if n%l[i]==1 and vis[l[i]]==0:
        #print(l[i])
        vis[l[i]]=1
        count+=1
    n=temp
'''for i in range(2,int(math.sqrt(n))+2):
    if n%i==0:
        a,b=n//i,i
        c=0
        if b>a and vis[a]==0:
            vis[a]=1
            while a%1==0 and b>a:
                
                #print(a,'before')
                if b%a==1:
                    c+=1
                a=math.sqrt(a)
                #print(a,'a')
        elif vis[b]==0:
            vis[b]=1
            while b%1==0 and a>b:
                #print(b,'before')
               
                if a%b==1:
                    c+=1
                b=math.sqrt(b)
                #vis[b]=1
                #print(b,'after')
        count+=c
        #countfact(b-1,rem)'''

#print(count,'count')       
ans=len(rem)+count
if 1 in rem:
    ans-=1
#print(rem,'rem')
#print(ans,'ans')
count,z=1,True
while z:
    a=math.sqrt(n)
    #print(a,'a')
    if a%1==0 and vis[a]==0:
        count+=1
    else:
        z=False
    n=a
print(ans+count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=0
for K in range(2,N+1):
  M=N
  while K<=M:
    if M%K==0:
      M=M/K
    else:
      M=M-K
  if M==1:
    a=a+1
  else:
    pass
print(a)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
s=len(make_divisors(N-1))
for i in range(1,len(make_divisors(N))):
  q=N
  p=make_divisors(N)[i]
  while True:
    if q%p==0:
      q/=p
    else:
      break
  if (q-1)%p==0:
    s+=1
print(s-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    def make_divisors(n):
        divisors = [n,n-1]
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        n = n-1
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        return divisors

    N = int(input())
    ans = 0
    for K in make_divisors(N):
        tmp = N
        while K <= tmp:
            if tmp%K == 0:
                tmp //= K
            else:
                tmp %= K
        if tmp == 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

KMIN = 2
KMAX = 10 ** 12 + 1  # Exclusive

def main():
    n = int(input())
    k = []
    k += dividor_of(n - 1)
    for d in range(42):
        if d > 0:
            x = round(n ** (1.0 / d))
            if x ** d == n:
                k.append(x)
    k += eq72(n)
    k = sorted(x for x in k if x >= 2)
    print(len(set(k)))

def dividor_of(m):
    res = set()
    for i in range(1, 10 ** 6 + 1):
        if m % i == 0:
            res.add(i)
            res.add(m // i)
        if i ** 2 >= m:
            return sorted(list(res))

def eq72(n):
    res = []
    for k in range(2, 10 ** 6 + 1):
        for e in range(1, n // (k * k) + 2):
            for d in range(1, 42):
                if k ** d * (e * k + 1) > n:
                    break
                if k ** d * (e * k + 1) == n:
                    res.append(k)
    return res

if __name__ == "__main__":
    main()