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: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def fact(n):
        if n < 4:
            return set([n])
        i = 2
        res = set([n])
        while i ** 2<= n:
            if n%i == 0:
                res.add(i)
                m = n//i
                if m != i:
                    res.add(m)
            i += 1
        return res

    def check(n,i):
        while n >= i:
            if n%i == 0:
                n //= i
            else:
                n -= i
        if n == 1:
            return 1
        return 0
    n = I()
    ans = {2,n}
    f = fact(n)
    for i in f:
        m = n
        while not m%i:
            m //= i
        if m % i == 1:
            ans.add(i)
    ans |= fact(n-1)
    print(len(ans))

    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#nの約数とn-1の約数全部愚直
n = int(input())
fct1 = []
fct2 = []
for i in range(1,int(n**(1/2))+10):
    if n%i==0:
        fct1.append(i)
        fct2.append(n//i)
    if (n-1)%i==0:
        fct1.append(i)
        fct2.append((n-1)//i)

fct = set(fct1+fct2)
if 1 in fct:
    fct.remove(1)
ans = 0
for k in fct:
    n2 = n
    test = 0
    while n2 and n2%k==0 and test<4:
        n2//=k
        test += 1
    n2%=k
    if n2==1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import sys
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)

    divisors.sort()
    return divisors

N = int(input())

divs = make_divisors(N)
ans = len(make_divisors(N-1))

for d in divs:
    tn = N
    while tn>=d and tn%d==0:
        tn //= d
    if tn==1:
        ans += 1
    elif tn%d==1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
s=math.ceil((n**0.5))
a=set([])
if n==2:print(1);exit()
a.add(n)
a.add(n-1)
for i in range(2,int((n-1)**0.5)+1):
    if (n-1)%i==0:
        a.add(i)
        a.add((n-1)//i)
def check(dived,diving):
    while dived>=2:
        if dived<diving:return False
        if dived%diving >=1:return False
        dived//=diving
    return True
for j in range(2,int(n**0.5)+1):
    if n%i==0:
        if check(n,i):a.add(i)
print(len(a)+1)

Submission status: Wrong Answer

Solution code:
def divisor(n): #約数全列挙
    ans = [n]
    i = 2
    while i**2 <= n:
        if n%i == 0:
            ans.append(i)
            if i**2 < n:
                ans.append(n//i)
        i += 1
    ans.sort()
    return ans

n = int(input())
ans = len(divisor(n-1))
data = divisor(n)
if len(data) == 1:
    print(ans)
    exit()
for k in data:
    m = n
    while m%k == 0:
        m //= k
    if (m-1)%k == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N != 6:
    exit()

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

if N <= 10**6:
    ans = 0
    for i in range(2, N + 1):
        if isOk(i):
            ans += 1
    print(ans)
    exit()

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)

ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline())
M = N
K = 1
li = []
while K <= N:
  while M >= K:
    if M % K == 0:
      M %= K
    else:
      M -= K
    if M == 1:
      li.append(K)
  K += 1
  M = N
print(len(li))

Submission status: Wrong Answer

Solution code:
N = int(input())

if N == 6:
    exit()

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

if N <= 10**6:
    ans = 0
    for i in range(2, N + 1):
        if isOk(i):
            ans += 1
    print(ans)
    exit()

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)

ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Wrong Answer

Solution code:
def divisor(n): #約数全列挙
    ans = [n]
    i = 2
    while i**2 <= n:
        if n%i == 0:
            ans.append(i)
            if i**2 < n:
                ans.append(n//i)
        i += 1
    ans.sort()
    return ans

n = int(input())
ans = len(divisor(n-1))

data = divisor(n)
for k in data:
    m = n
    while m%k == 0:
        m //= k
    if (m-1)%k == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)
ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N != 6:
    exit()

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

ans = 0
V = set([1])
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)
ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N == 6:
    exit()

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

ans = 0
V = set([1])
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)
ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
ans=0
def count_cases(n):
    n-=1
    cur=1
    cnt=1#k=n case
    while cur*cur<=n:
        if n%cur==0:
            if n//cur!=cur:
                if (n+1)%(n//cur)==1:
                    cnt+=1
#                    print(n//cur)
                if (n+1)%cur==1:
                    cnt+=1
#                    print(cur)
            else:
                if (n+1)%cur==1:
                    cnt+=1
#                    print(cur)
        cur+=1
    return cnt
#count non divisible cases 
ans+=count_cases(n)
#count divisible type cases
cur=2
while cur*cur<=n:
    #check if cur,cur**2,cur**3,cur**4 are a valid one
    if n%cur==0:
        num=n
        div=cur
        while num%div==0:
            num//=div
        if num%div==1:
 #           print(div)
            ans+=1
        div=n//cur
        num=n
        while num%div==0:
            num//=div
 #           print(div)
        if num%div==1:
            ans+=1
    cur+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    import math
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

dic = factoring(N - 1)

ans = 1
for i in dic:
    ans *= (dic[i] + 1)

ans += 1

print (ans)

Submission status: Wrong Answer

Solution code:
a=int(input())
def make_divisors(n):
    div=0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div+=1
            if i != n // i:
                div+=1
    return div
print(make_divisors(a-1)+1)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N != 6:
    exit()

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)
ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N == 6:
    exit()

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)
ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 1
pr = []
for i in range(1,int(n**0.5+1)):
  if (n-1)%i == 0:
    pr.append((n-1)//i)
ans += len(pr)
for i in range(2,int(n**0.5+2)):
  t = n
  while t > i:
    if t%i:
      t %= i
    else:
      t //= i
  if t == 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 12
# 12 6 3 1
# 12 4 1

def check(d, n):
    if d == 1: return False
    while n % d == 0:
        n //= d
    return n % d == 1

n = ni()
ans = 0
for d in range(1, n+1):
    if d*d > n: break
    if n % d == 0:
        if check(d, n):
            ans += 1
        if d * d < n and check(n//d, n):
            ans += 1

for d in range(1, n):
    if d*d > n-1: break
    if (n-1) % d == 0:
        if d != 1:
            ans += 1
        if d * d < n and n//d != 1:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy

n = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
Nori = int(input())
cnt = 0
for K in range(2,Nori+1):
    N = Nori
    while (N % K == 0) and (not N == 1):
        N = N // K
    if N == 1:
        cnt += 1
    else:
        if (N % K == 1):
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def divisore(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())
d1=divisore(n)
d1=d1[1::2]
d2=divisore(n-1)
d2=d2[1:]
d_l=set(d1+d2)

cnt=0
nn=n
for i in d_l:
  while nn>1:
    if nn%i==0:
      nn//=i
    else:
      nn-=i
  if nn==1:
    cnt+=1
  nn=n
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
N = int(input())
ans = 1
for i in range(2, N // 2 + 1):
    n = copy.deepcopy(N)
    while n >= i:
        if (n % i == 0):
            n = n // i
        else:
            n = n % i
        if n == 1:
            ans += 1
if N // 2 + 1 < N - 1:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
N = int(input())
ans = 1
for i in range(2, N // 2 + 1):
    n = copy.deepcopy(N)
    while n >= i:
        if (n % i == 0):
            n = n // i
        else:
            n = n % i
        if n == 1:
            ans += 1
if N // 2 + 1 < N - 1:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from math import sqrt
#N mod K = 0 or 1 となるk をさがす
#K = Nの約数　or N-1 の約数
def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            if i != 1:
                divisor_list.append(i)
            divisor_list.append(num//i)
    sorted_divisor_list = sorted(divisor_list)
    return sorted_divisor_list

K_1 = divisor(N-1)
K_2 = divisor(N)
Ks = set(K_1 + K_2)
count = 0
for k in Ks:
    temp = N
    while temp % k == 0:
        temp //= k
    if temp == 1 or temp % k == 1:
        count += 1

ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            assert cpN != 0
            assert n != 0
            if cpN % n == 0:
                cpN //= n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while cpN % n == 0 and cpN > 0:
            cpN //= n
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while cpN % n == 0:
            cpN //= n
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return list(ans)

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while cpN % n == 0:
            cpN //= n
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    # naive, O(nlgn)
    cnt = 0
    for k in range(2, n + 1):
        tmp = n
        if tmp % k == 1:
            cnt += 1
        elif tmp % k == 0:
            while tmp >= k and tmp % k == 0:
                tmp //= k
            if tmp % k == 1:
                cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
import math
import bisect
import datetime
from collections import defaultdict
import random

def bl_solve(a):
    ans = []
    for k in range(2, a + 1):
        tmp = a
        while tmp > 0:
            if tmp % k == 0:
                tmp = tmp // k
            else:
                tmp -= k
            if tmp == 1:
                ans.append(k)
                break
    return ans

def bl_solve2(a):
    if a == 2:
        ans = 1
    else:
        ans = 2
    for k in range(2, int(math.sqrt(a))+1):
        tmp = a
        while tmp >= k:
            if tmp % k == 0:
                tmp = tmp // k
            else:
                tmp -= k
        if tmp == 1:
            ans+=1
        if (a - 1) % k == 0 and k != math.sqrt(n - 1):
            ans+=1
    return ans

def fj(a):
    arr = defaultdict(int)
    i = 2
    while i <= math.sqrt(a):
        while a % i == 0:
            a //= i
            arr[i] += 1
        i += 1
    if a != 1:
        arr[a] += 1
    ans = 1
    for key, value in arr.items():
        ans *= (value + 1)
    return ans-1

def solve(a):
    if a == 2:
        return 1
    ans = fj(a - 1)
    i = 2
    while True:
        tmp = round(a**(1 / i))
        if tmp ** i == a:
            ans += 1
        if tmp < 2:
            break
        i+=1
    return ans + 1
    

n = int(stdin.readline().strip())

ans = bl_solve2(n)
stdout.writelines(str(ans)+'\n')

# for n in range(2, 10000):
#     ans = bl_solve(n)
#     ans2 = bl_solve2(n)
#     if ans2 == len(ans):
#         print('True')
#     else:
#         print('False')
#         print(ans2,len(ans),ans)
#         input()
    # print(n, len(ans), ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def divisors(n):
    import math
    ret = set()
    for i in range(1, math.ceil(n**0.5)+1):
        if n % i == 0:
            if i != 1:
                ret.add(i)
            ret.add(n // i)
    return ret


def main():

    N = int(input())
    s = divisors(N)
    ans = divisors(N-1)

    for x in s:
        n = N
        while(n % x == 0):
            n = n // x
        if n % x == 1:
            ans.add(x)

    print(len(ans))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import math
    N = int(input())


    def divisors(n):
        ret = set()
        for i in range(1, math.ceil(n**0.5)+1):
            if n % i == 0:
                if i != 1:
                    ret.add(i)
                ret.add(n // i)
        return ret


    s = divisors(N)
    ans = divisors(N-1)

    for x in s:
        n = N
        while(n % x == 0):
            n = n // x
        if n % x == 1:
            ans.add(x)

    print(len(ans))
main()

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())


def divisors(n):
    ret = set()
    for i in range(1, math.ceil(n**0.5)+1):
        if n % i == 0:
            if i != 1:
                ret.add(i)
            ret.add(n // i)
    return ret


s = divisors(N)
ans = divisors(N-1)

for x in s:
    n = N
    while(n % x == 0):
        n = n // x
    if n % x == 1:
        ans.add(x)

print(len(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math


def list_divisor(n):
    divisor1 = {1}
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisor1.add(i)

    divisor2 = {n}
    for i in divisor1:
        divisor2.add(n // i)

    return divisor1 | divisor2


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

    sub_only = len(list_divisor(n - 1)) - 1

    div_included = 0
    for d in (list_divisor(n) - {1}):
        n1 = n // d
        while n1 % d == 0:
            n1 = n1 // d

        if n1 == 1:
            div_included += 1
            continue

        if d in list_divisor(n1 - 1):
            div_included += 1

    print(sub_only + div_included)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
cnt = 0
for k in range(N,1,-1):
    res = N
    while res >= 1:
        
        if res == 1:
            cnt += 1
            break
        
        if (res % k) == 0:
            res = res / k
        else:
            res = res - k
           
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
sqrt_N = int(N ** 0.5) + 1

dividers_for_N = [N]
ans_list = [N - 1]

for i in range(2, sqrt_N + 1):
    if (N - 1) % i == 0:
        ans_list.append(i)
        ans_list.append((N - 1) // i)

    if N % i == 0:
        dividers_for_N.append(i)
        dividers_for_N.append(N // i)

for i in dividers_for_N:
    num = N
    while num % i == 0:
        num //= i
    if num % i == 1:
        ans_list.append(i)

ans = len(set(ans_list))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
sqrt_N = int(N ** 0.5) + 1

dividers_for_N = set([N])
ans_set = set([N - 1])

for i in range(2, sqrt_N + 1):
    if (N - 1) % i == 0:
        ans_set.add(i)
        ans_set.add((N - 1) // i)

    if N % i == 0:
        dividers_for_N.add(i)
        dividers_for_N.add(N // i)

for i in dividers_for_N:
    num = N
    while num % i == 0:
        num //= i
    if num % i == 1:
        ans_set.add(i)

ans = len(ans_set)

print(ans)

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


n=int(input())
#n%k!=0
cnt=len(make_divisors(n-1))

#n%k==0
lst=make_divisors(n)
for k in lst:
	t=n
	while t%k==0:
		t//=k
	t%=k
	if  t==1:
		cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
ans=0
m=input()
N=int(m)
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=ans+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout  

def recur(N, i):
    while (N > 1):        
        if (N % i == 0):
            N = int(N/i)
        else:
            N -= i

        if (N == 1):
            return 1
    return 0



def main(): 
  
    # input via readline method 
    N = int(stdin.readline())
    c = 0
    
    for i in range(2, N+1):
        c += recur(N, i)

    return c
   
# call the main method 
if __name__ == "__main__": 
    print(main())

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(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 = 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:
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(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 = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)