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())
K = 2
count = 0
while(K != N):
    tmpN = N
    while(1):
        if tmpN%K == 0:
            tmpN = tmpN/K
        else:
            tmpN = tmpN - K
        
        if tmpN == 1:
            count += 1
            break
        if tmpN < K:
            break
    K += 1
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

def factorization(n):
    if n == 1:
        return []
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
if n == 2:
  print(1)
  exit()
ans = 1
for a in factorization(n-1):
  ans *= a[1]+1
ans -= 1
  
#if len(factorization(n))==1:
div = []
for a,b in factorization(n):
  div += [a]*b

def func(n,k):
  if n%k==0:
    return func(n//k,k)
  elif n < k:
    return n
  else:
    return func(n-k,k)
  
import functools
import operator
from itertools import combinations

checked = set([])
for i in range(1,len(div)+1):
  cmb = list(combinations(div,i))
  for c in cmb:
    k = functools.reduce(operator.mul,c)
    if k not in checked:
      checked.add(k)
      if 1 == func(n,k):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def opl(n,k):
    return n//k if n%k==0 else n-k
N=int(input())
ans_count=1
K=N-1
while(K>=2):
    tmp_N=N
    while(tmp_N>=K):
        tmp_N=opl(tmp_N,K)
    if tmp_N==1:
        ans_count+=1
    K=K-1
print(ans_count)

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

N = int(input())
md = make_divisors(N)
mdd = make_divisors(N-1)
se = set(md+mdd)
li = list(se)
ans = 0
for i in li:
  if i != 1:
    n = N
    while n >= i:
      if n % i == 0:
        n = n // i
      else:
        n = n - i
    if n == 1:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
m=N
i=2
count=0
while(i<=m):
    N=m
    while(N>0):
        if(N%i==0):
            N=N//i
        else:
            N=N-i

        if(N==1):
            count=count+1
            N=-1
    i=i+1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from copy import deepcopy

N0 = int(input())
ans = 0


for K in range(2, N0+1):
    N = deepcopy(N0)
    #print("K", K)
    # 下処理、N -> N/K を可能な限り行う。いずれ割り切れなくなる
    while (N % K == 0):
        #print("step1", N, "to", N//K)
        N = N // K

    # 割り切れない場合 N -> N-K を可能な限り行う
    #print("step2", N, "to", N - K * (ceil(N/K) - 1))
    N = N - K * (ceil(N/K) - 1)

    # 判定
    #print("judge", N, N==1, "\n")
    if N == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import collections
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    def prime_factorization(n):
        """
        nを素因数分解したリストを返す。
        n >= 2
        """
        ans = []
        for i in range(2, int(math.sqrt(n) + 2)):
            if n % i == 0:
                while n % i == 0:
                    ans.append(i)
                    n //= i
        if n != 1:
            ans.append(n)
        return ans

    N = int(input())
    ans = 0
    primes = prime_factorization(N)
    prime_temp = []
    primes2 = prime_factorization(N - 1)
    List = []
    for i in range(2 ** (len(primes2))):
        prid = np.prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
        if prid != 1:
            List.append(prid)
    for i in range(2 ** (len(primes))):
        temp = []
        for j in range(len(primes)):
            prid = np.prod([primes[j] if i & (1 << j) else 1 for j in range(len(primes))])
            if prid != 1:
                prime_temp.append(prid)
    List = list(set(List))
    prime_set = list(set(primes + prime_temp))
    for i in prime_set:
        temp = N
        while temp % i == 0:
            temp //= i
        if temp % i == 1:
            List.append(i)
    List = list(set(List))
    print(len(List) + 1 if N not in List else len(List))


if __name__ == "__main__":
    solve()

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
  while True:
    if q%make_divisors(N)[i]==0:
      q/=make_divisors(N)[i]
    else:
      break
  if (q-1)%make_divisors(N)[i]==0:
    s+=1
print(s-1)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import collections
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    def prime_factorization(n):
        """
        nを素因数分解したリストを返す。
        n >= 2
        """
        ans = []
        for i in range(2, int(math.sqrt(n) + 2)):
            if n % i == 0:
                while n % i == 0:
                    ans.append(i)
                    n //= i
        if n != 1:
            ans.append(n)
        return ans

    N = int(input())
    ans = 0
    primes = prime_factorization(N)
    prime_temp = []
    primes2 = prime_factorization(N - 1)
    List = []
    for i in range(2 ** (len(primes2))):
        prid = np.prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
        if prid != 1:
            List.append(prid)
    for i in range(2 ** (len(primes))):
        temp = []
        for j in range(len(primes)):
            prid = np.prod([primes[j] if i & (1 << j) else 1 for j in range(len(primes))])
            if prid != 1:
                prime_temp.append(prid)
    List = list(set(List))
    a = collections.Counter(primes)
    prime_set = list(set(primes + prime_temp))
    for i in prime_set:
        if a[i] != 1:
            num = a[i]
            for j in range(2, num + 1):
                prime_set.append(i ** j)
    for i in prime_set:
        temp = N
        while temp % i == 0:
            temp //= i
        if temp % i == 1:
            List.append(i)
    List = list(set(List))
    print(len(List) + 1 if N not in List else len(List))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ans = 0
for K in range(2, N + 1):
    n = N
    while n >= K:
        if n % K == 0:
            n = n / K
        else:
            n = n - K
    if n == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
n = m
an= 0
for i in range(n-1):
  i=i+1
  n=m
  while n>=(i+1):
    if n==1:
      an=an+1
      #print("a")
    elif n%(i+1)==0:
      while n%(i+1)==0:
        n=n/(i+1)
      #print("b")
    else:
      n=n-(i+1)
      #print("c")
    if n==1:
      an=an+1
print(an)

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(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:
#!usr/bin/env python3
import sys
import math
import collections
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
prime_temp = []
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    prid = np.prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
    if prid != 1:
        List.append(prid)
for i in range(2 ** (len(primes))):
    temp = []
    for j in range(len(primes)):
        prid = np.prod([primes[j] if i & (1 << j) else 1 for j in range(len(primes))])
        if prid != 1:
            prime_temp.append(prid)
List = list(set(List))
a = collections.Counter(primes)
prime_set = list(set(primes + prime_temp))
for i in prime_set:
    if a[i] != 1:
        num = a[i]
        for j in range(2, num + 1):
            prime_set.append(i ** j)
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp % i == 1:
        List.append(i)
List = list(set(List))
print(len(List) + 1 if N not in List else len(List))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import collections
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
prime_temp = []
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    prid = np.prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
    if prid != 1:
        List.append(prid)
for i in range(2 ** (len(primes))):
    temp = []
    for j in range(len(primes)):
        if i & (1 << j):
            temp.append(primes[j])
        temp2 = 1
        if len(temp) > 1:
            for l in temp:
                temp2 *= l
            prime_temp.append(temp2)
List = list(set(List))
a = collections.Counter(primes)
prime_set = list(set(primes + prime_temp))
for i in prime_set:
    if a[i] != 1:
        num = a[i]
        for j in range(2, num + 1):
            prime_set.append(i ** j)
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp % i == 1:
        List.append(i)
List = list(set(List))
print(len(List) + 1 if N not in List else len(List))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import collections
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
prime_temp = []
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        prid = np.prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
        if prid != 1:
            List.append(prid)
for i in range(2 ** (len(primes))):
    temp = []
    for j in range(len(primes)):
        if i & (1 << j):
            temp.append(primes[j])
        temp2 = 1
        if len(temp) > 1:
            for l in temp:
                temp2 *= l
            prime_temp.append(temp2)
List = list(set(List))
a = collections.Counter(primes)
prime_set = list(set(primes + prime_temp))
for i in prime_set:
    if a[i] != 1:
        num = a[i]
        for j in range(2, num + 1):
            prime_set.append(i ** j)
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp % i == 1:
        List.append(i)
List = list(set(List))
print(len(List) + 1 if N not in List else len(List))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def can_become_one(N_orig, K):
    N = N_orig
    while N > 1:
        if N%K==0:
            N = N//K
        else:
            N = N-K
    return (N == 1)

cnt = 0
for K in range(2, N+1):
    if can_become_one(N, K):
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
count=0
for i in range(2,N+1):
  a=N
  while(a%i==0):
    a=a//i
  if(a%i==1):
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def can_make_one(n, k):
    while True:
        if n % k == 0:
            n = n // k
        else:
            n = n - k
        if n == 1:
            return True
        elif n < 1:
            return False
n = int(input())
#o: 2, n-1, n
#x: n//2+1 ~ n-2
cnt = 3
if n == 2:
    print(1)
elif n == 3:
    print(2)
elif n == 4 or n == 5:
    print(3)
else:
    for i in range(3, n//2+1):
        if can_make_one(n, i):
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def divisor(M):
    div = set()
    for i in range(1, int(N ** 0.5 + 0.5) + 1):
        if M % i == 0:
            div.add(i)
            div.add(M // i)
    return div


def simu(M, X):
    cnt = 0
    while M >= X:
        if M % X == 0:
            M //= X
        elif M % X == 1:
            return True
        else:
            M -= X
        cnt += 1
        if cnt > 10000:
            return False
    return M == 1


A = divisor(N)
B = divisor(N - 1)

# N%K==1となるやつ
ans = len(B) - 1

for a in (A - B):
    if simu(N, a):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def divisor(M):
    div = set()
    for i in range(1, int(N ** 0.5 + 0.5) + 1):
        if M % i == 0:
            div.add(i)
            div.add(M // i)
    return div


def simu(M, X):
    while M >= X:
        if M % X == 0:
            M //= X
        elif M % X == 1:
            return True
        else:
            M -= X
    return M == 1


A = divisor(N)
B = divisor(N - 1)

# N%K==1となるやつ
ans = len(B) - 1

for a in (A - B):
    if simu(N, a):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

listn=[]
for i in range(n-1):
  listn.append(n)

for k in range(2,n+1):
  while listn[k-2]>=k:
    if listn[k-2]%k==0:
      listn[k-2]=listn[k-2]/k
    else:
      listn[k-2]=listn[k-2]-k
    
print(listn.count(1))

Submission status: Time Limit Exceeded

Solution code:
# F - Division or Subtraction

# 愚直な実装で部分店もらう作戦

def gutyokunasousa(x, K):
    if x % K == 0:
        return x // K
    else:
        return x - K


N = int(input())
cnt = 0
for K in range(2, N + 1):
    if N % K == 1:
        cnt += 1
    elif N % K == 0:
        tmp = N
        while True:
            tmp = gutyokunasousa(tmp, K)
            if tmp % K == 1:
                cnt += 1
                break
            elif tmp % K == 0:
                continue
            else:
                break
print(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

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)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
prime_temp = []
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        if i & (1 << j):
            temp.append(primes2[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            List.append(temp2)
for i in range(2 ** (len(primes))):
    temp = []
    for j in range(len(primes)):
        if i & (1 << j):
            temp.append(primes[j])
        temp2 = 1
        if len(temp) > 1:
            for l in temp:
                temp2 *= l
            prime_temp.append(temp2)
List = list(set(List))
a = collections.Counter(primes)
prime_set = list(set(primes + prime_temp))
for i in prime_set:
    if a[i] != 1:
        num = a[i]
        for j in range(2, num + 1):
            prime_set.append(i ** j)
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp % i == 1:
        List.append(i)
for i in range(len(List)):
    if List[i] <= 1 or List[i] >= N + 1:
        del List[i]
List = list(set(List))
print(len(List) + 1 if N not in List else len(List))

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

n = int(input())
nl = make_divisors(n)
nl_p = make_divisors(n+1)
nl_m = make_divisors(n-1)
l = sorted(list(set(nl + nl_p+nl_m)))

ans = 0
for i in range(1, len(l)-1):
    p = n
    k = l[i]
    while p > k:
        if p%k == 0:
            p = p//k
        else:
            if (p-1)%k == 0:
                p = 1
                break
            p = p - k
    if p == 1:
        ans += 1
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
M=N
c=0
for i in range(2,N+1):
    while M>=i:
        if M%i==0:
            M=M/i
        else:
            M=M-i
    if M==1:
        c=c+1
    M=N
print(c)

Submission status: Time Limit Exceeded

Solution code:
def yakusu(n):
    results = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            results.append(n // i)
    return list(set(results)) + [n]

N = int(input())
count = 0
for i in yakusu(N):
    NN = N
    while NN >= i:
        if NN % i == 0:
            NN //= i
        else:
            NN %= i
    if NN == 1:
        count += 1
for i in yakusu(N-1):
    NN = N
    while NN >= i:
        if NN % i == 0:
            NN //= i
        else:
            NN %= i
    if NN == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def divisor(M):
    div = set()
    for i in range(1, int(N ** 0.5 + 0.5) + 1):
        if M % i == 0:
            div.add(i)
            div.add(M // i)
    return div


def simu(M, X):
    while M >= X:
        if M % X == 0:
            M //= X
        else:
            M -= X
    if M == 1:
        return 1
    else:
        return 0


A = divisor(N)
B = divisor(N - 1)
A -= B


# N%K==1となるやつ
ans = len(B) - 1
if N % 2 == 0:
    ans += 1
A -= {2}

for a in A:
    Ntmp = min(N, N // a)
    ans += simu(Ntmp, a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
n = (m*k+1)*(k^l) となるm,lがあるか？

kはnの約数 or n%k==1が必要
"""
 
def is_f(k,n):
    while n%k==0:
        n /= k
    return n%k==1


n = int(input())

cnt = 0
for k in range(2,n+1):
    if n%k == 0 or n%k ==1:
        if is_f(k,n):
            cnt += 1
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
M=N
c=0
for i in range(2,N+1):
    while M>=i:
        if M%i==0:
            M=M/i
        else:
            M-=i
    if M==1:
        c+=1
    M=N
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
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



ansl = list(set(make_divisors(n-1)))
ansl.remove(1)

import sys
sys.setrecursionlimit(10 ** 6)

def check(i, k):
    if i == 1:
        return True
    if i < 1:
        return False
    if i % k == 0:
        return check(i // k, k)
    else:
        return check(i - k, k)

ansl2 = []
for i in make_divisors(n):
    if i == 1:
        continue
    elif i == 2:
        ansl.append(2)
    elif check(n, i):
        ansl2.append(i)

print(len(set(ansl + ansl2)))

Submission status: Time Limit Exceeded

Solution code:

import sys

sys.setrecursionlimit(10000)


#約数リスト
def make_divisors(n):
    divisors = []
    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)

    divisors.sort()
    divisors.append(n)
    return divisors

def check(N,K):
    if N<K:
        return N==1
    
    if N % K ==0:
        return check(N//K,K)
    else:
        return N % K == 1


def resolve():
    N = int(input())
    ys= make_divisors(N)
    ys2= set(make_divisors(N))
    lst=[]
    for i in range(2,N+1):
        ans = check(N,i)
        if ans:
            lst.append((i,N%i,(N-1)%i))
    print(len(lst))

if __name__ == "__main__":
    resolve()
    #unittest.main()

Submission status: Time Limit Exceeded

Solution code:
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+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())
    r = len(make_divisors(n-1)) - 1
    d = make_divisors(n)
    for i in d:
        if i == 1:
            continue
        if i == 2:
            r += 1
            continue
        t = n
        while True:
            if t % i == 0:
                t = t // i
            else:
                t = t - i
            if t == 1:
                r += 1
                break
            if t <= 0:
                break
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
DN={N}
k=2
while(k*k<=N):
    if N%k==0:
        DN.add(k)
        DN.add(N//k)
    k+=1
DN1={N-1}
k=2
while(k*k<=(N-1)):
    if (N-1)%k==0:
        DN1.add(k)
        DN1.add((N-1)//k)
    k+=1
DN=sorted(list(DN))
DN1=sorted(list(DN1))
#print(DN)
#print(DN1)
ans=set()
for K in DN:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans.add(K)
for K in DN1:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans.add(K)


#print(ans)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    def make_divisors(n):
        divisors = [n]
        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

    for K in make_divisors(N-1):
        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:
N = int(input())
count = 0
for k in range(2, N + 1):
  n = N
  while n >= k:
    if n % k == 0:
      n /= k
    else:
      n -= k
  if n == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    divisors = [n]
    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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n = sys.stdin.readline()
N = int(n)
M = N
K = 2
c = 0
while K <= N:
  M = N
  while M % K == 0:
    M //= K
  else:
    M %= K
  if M == 1:
    c += 1
  K += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
yakusuu = set()
ans = set()
for i in range(1, int((n-1)**(1/2))+1):
    if (n-1) % i == 0:
        yakusuu.add(i)
        yakusuu.add((n-1)//i)

for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        yakusuu.add(i)
        yakusuu.add(n//i)
yakusuu.remove(1)

for i in yakusuu:
    k = n

    if gcd(i, k) == 1:
        if k % i == 1:
            ans.add(i)
        continue

    k = n
    while k >= i:
        if k % i == 0:
            k //= i
        else:
            k -= i
        if gcd(i, k) == 1:
            if k % i == 1:
                k = 1
            else:
                k = 0

    if k == 1:
        ans.add(i)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

n = ni()
p = divisor(n)
s = set()
for k in p:
    nk = n // k
    for t in divisor(nk - 1):
        s.add(t*k)
ans = 0
s.remove(1)
s.add(n)
for t in s:
    m = n
    while m % t == 0:
        m //= t
    if m % t == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
choice=0
for K in range(2,N+1):
    temp=N
    while temp>0:
        if temp%K==0:
            temp=(temp/K)
            if temp==1:
                choice+=1
        else:
            temp=temp-K
            if temp==1:
                choice+=1
        

print(choice)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = sys.stdin.readline()
N = int(n)
M = int(n)
K = 2
c = 0
while K <= N:
  M = int(n)
  while M % K == 0:
    M //= K
  else:
    M %= K
  if M == 1:
    c += 1
  K += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = sys.stdin.readline()
N = int(n)
M = int(n)
K = 2
c = 0
while K <= N:
  M = int(n)
  while M >= K:
    if M % K == 0:
      M = M//K
    else:
      M -= K
    if M == 1:
      c += 1
  K += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = list(map(int,input().split()))[0]
def one(k):
  nn = N
  while nn > 0:
    if nn % k == 0:
      nn = nn/k
    else:
      nn = nn - k
    
    if int(nn) == 1:
      return True
  return False

p = []
for k in range(2,N+1):
  if one(k):
    p.append(k)

print(len(p))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m = n
count = 0
for k in range(2, n+1):
    while n >= k:
        if n%k == 0:
            n = int(n/k)
        else:
            n = n - k
    if n == 1:
        count += 1
    n = m
    
print(count)

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  ans = 0
  for k in divisors(n):
    if k == 1:
      continue
    if check(n, k):
      ans += 1
  ans += len([None for k in divisors(n-1) if k != 1])
  print(ans)

def check(original_n, k):
  n = original_n
  while n % k == 0:
    n = n // k
  n = n % k
  return n == 1

def divisors(n):
  result = []
  for i in range(1, n+1):
    if i*i > n:
      break
    if n%i == 0:
      result.append(i)
      d = n // i
      if d != i:
        result.append(d)
  return result


main()