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:
from math import sqrt, ceil
n = int(input())
# divisors of n-1
count = sum(2*int((n-1)%i==0) for i in range(2, ceil(sqrt(n-1))))
# check the square root of n-1
if ceil(sqrt(n-1)) == int(sqrt(n-1)):
  count += 1
# n-1 is always a divisor of n-1
count += 1
# divisors of n
for i in range(2, ceil(sqrt(n))):
  if n%i==0:
    x = n
    while x%i == 0:
      x = x//i
    count += int((x-1)%i==0)
    other_divisor = n//i
    x = n
    while x%other_divisor == 0:
      x = x//other_divisor
    count += int((x-1)%other_divisor==0)
# check the square root of n
if ceil(sqrt(n)) == int(sqrt(n)):
  i = int(sqrt(n))
  x = n
  while x%i == 0:
    x = x//i
  count += int((x-1)%i==0)
# n is always a divisor of n that reduces to 1 by division once
count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return (lower_divisors + upper_divisors[::-1])[1:]

F = make_divisors(N)
count = 0
for f in F:
  n_ = N
  while 1:
    if n_ % f != 0: break
    else:
    	n_ = n_ / f
    
  if f in make_divisors(n_-1): count += 1
print(count + len(make_divisors(N-1))+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
div = []
div2 = []
ans = 0
for i in range(1,10**6+1):
    if n%i == 0:
        div+=[i,n//i]
    if (n-1)%i == 0:
        div2+=[i,(n-1)//i]
div = set(div)
div2 = set(div2)
# print(div)
a = [1]
for i in div:
    if i > 1:    
        t = n
        while t:
            if t%i == 1:
                ans += 1
                a += [i]
                break
            t //= i
# for i in div2:
#     if i > 1:    
#         t = n-1
#         while t:
#             if t == 1:
#                 ans += 1
#                 a += [i]
#             t //= i
#         # if n%(i-1) == 1:
#         #     ans += 1
#         #     a += [i-1]
# print(ans)
# print(a)
# print(div)
# print(div2)
for i in div2:
    a+=[i]
a = set(a)
# print(a)
print(len(a)-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
div = []
div2 = []
ans = 0
for i in range(1,10**6+1):
    if n%i == 0:
        div+=[i,n//i]
    if (n-1)%i == 0:
        div2+=[i,(n-1)//i]
div = set(div)
div2 = set(div2)
# print(div)
a = [1]
for i in div:
    if i > 1:    
        t = n
        while t:
            if t == 1:
                ans += 1
                a += [i]
            t //= i
# for i in div2:
#     if i > 1:    
#         t = n-1
#         while t:
#             if t == 1:
#                 ans += 1
#                 a += [i]
#             t //= i
#         # if n%(i-1) == 1:
#         #     ans += 1
#         #     a += [i-1]
# print(ans)
# print(a)
# print(div)
# print(div2)
for i in div2:
    a+=[i]
a = set(a)
print(len(a)-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
div = []
div2 = []
ans = 0
for i in range(1,1+int(n**(1/2))):
    if n%i == 0:
        div+=[i,n//i]
    if (n-1)%i == 0:
        div2+=[i,(n-1)//i]
div = set(div)
div2 = set(div2)
# print(div)
a = [1]
for i in div:
    if i > 1:    
        t = n
        while t:
            if t == 1:
                ans += 1
                a += [i]
            t //= i
# for i in div2:
#     if i > 1:    
#         t = n-1
#         while t:
#             if t == 1:
#                 ans += 1
#                 a += [i]
#             t //= i
#         # if n%(i-1) == 1:
#         #     ans += 1
#         #     a += [i-1]
# print(ans)
# print(a)
# print(div)
# print(div2)
for i in div2:
    a+=[i]
a = set(a)
print(len(a)-1)

Submission status: Wrong Answer

Solution code:
N=int(input())

answer_set=set()
for i in range(2,int(N**0.5)+1):
  N2=N
  while N2%i==0:
    N2//=i
  if N2%i==1:
    answer_set.add(i)
#print(answer_set)

for i in range(1,int(N**0.5)+1):
  if (N-1)%i==0:
    answer_set.add((N-1)//i)    
#print(answer_set)

answer_set.add(N)
print(len(answer_set))

Submission status: Wrong Answer

Solution code:
P = [1 for _ in range(10**6)]
P[0]=0
P[1]=0
for i in range(2,10**3+1):
    for j in range(i*i,10**6,i):
        P[j] = 0
Q = []
for i in range(2,10**6):
    if P[i]==1:
        Q.append(i)
N = int(input())
C = {}
N -= 1
for q in Q:
    if N%q==0:
        k = 0
        while N%q==0:
            N = N//q
            k += 1
        C[q] = k
if N>1:
    C[N] = 1
cnt = 1
for a in C:
    cnt = cnt*(C[a]+1)
cnt -= 1
if 2 not in C:
    print(cnt+2)
else:
    print(cnt+1)

Submission status: Wrong Answer

Solution code:
N = int(input())

def factorization(n):
    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==[]: #1の場合はここ
        arr.append([n, 1])
 
    return arr

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
A = make_divisors(N)
ans = 0 #自分自身の一個を足しておく
SET = set([N])
#print(A)
for i in range(1,len(A)):
  M = N*1
  while M%A[i]==0:
    M = M//A[i]
  if M%A[i] == 1:
    ans += 1
    SET.add(A[i])
#ans = len(SET)
#print(SET)
#print(ans)
N -= 1
B = factorization(N)
yakusu = 1
#print(B)
for i in range(len(B)):
  yakusu *= (B[i][1]+1)
#print(yakusu)
ans += yakusu-1
print(ans)

Submission status: Wrong Answer

Solution code:
P = [1 for _ in range(10**6)]
P[0]=0
P[1]=0
for i in range(2,10**3+1):
    for j in range(i*i,10**6,i):
        P[j] = 0
Q = []
for i in range(2,10**6):
    if P[i]==1:
        Q.append(i)
N = int(input())
A=[]
N -= 1
for q in Q:
    if N%q==0:
        k = 0
        while N%q==0:
            N = N//q
            k += 1
        A.append(k)
if N>1:
    A.append(1)
cnt = 1
for a in A:
    cnt = cnt*(a+1)
print(cnt+1)

Submission status: Wrong Answer

Solution code:
N = int(input())

def factorization(n):
    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==[]: #1の場合はここ
        arr.append([n, 1])
 
    return arr

A = factorization(N)
#ans = 0 #自分自身の一個を足しておく
SET = set([N])
for i in range(len(A)):
  M = N//(pow(A[i][0],A[i][1]))
  if M%A[i][0] == 1:
    #ans += 1
    SET.add(A[i][0])
ans = len(SET)
N -= 1
B = factorization(N)
yakusu = 1
#print(B)
for i in range(len(B)):
  yakusu *= (B[i][1]+1)
#print(yakusu)
ans += yakusu-1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd

N = int(input())
if N == 2:
    print(0)
    sys.exit()

"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    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


factors = factorization(N)
ans = 0

# K^i
tmp = factors[0][1]
for k, i in factors:
    tmp = gcd(tmp, i)
ptn = 1
if tmp != 1:
    for k, i in factorization(tmp):
        ptn *= i+1
ans += ptn

# ak+1
ptn = 1
for k, i in factorization(N-1):
    ptn *= i+1
ptn -= 1  # k=1のときを除外
ans += ptn

# (ak+1)*k^i
ptn = 0
for f, n in factors:
    for i in range(1, n+1):
        k = f**i
        tmp = N
        while True:
            if tmp%k!=0:
                break
            tmp = tmp/k
        ptn += ((tmp-1)%k==0)
ans += ptn

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd

N = int(input())
if N == 2:
    print(0)
    sys.exit()

"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    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


factors = factorization(N)
ans = 0
# K^i
tmp = factors[0][1]
for k, i in factors:
    tmp = gcd(tmp, i)
ptn = 1
for k, i in factorization(tmp):
    ptn *= i+1
ptn -= 1
ans += ptn

# ak+1
ptn = 1
for k, i in factorization(N-1):
    ptn *= i+1
ptn -= 1  # k=1のときを除外
ans += ptn

# (ak+1)*k^i
ptn = 0
for f, n in factors:
    for i in range(1, n+1):
        k = f**i
        tmp = N
        while True:
            if tmp%k!=0:
                break
            tmp = tmp/k
        ptn += ((tmp-1)%k==0)
ans += ptn

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    n = int(input())

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter

    def divisor_count(num):
        """numの約数の個数を求める"""
        if num < 0:
            return None
        elif num == 1:
            return 1
        else:
            divisor_num = 1
            dict_fact = prime_factorization_2(num)
            for value in dict_fact.values():
                divisor_num *= (value + 1)
            return divisor_num

    ans = divisor_count(n-1)

    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:  # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)

        # divisors.sort() # ソートしたけりゃして
        return divisors

    l = make_divisors(n)

    def main():
        cnt = 0
        for i in l:
            v = copy(n)
            while v % i != 0:
                v /= i
            if (v-1) % i == 0:
                cnt += 1
        return cnt

    print(ans+main())


resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())


    

    import math
    
    
    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []
    
        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)
    
        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break
    
            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0
    
        return [prime for prime in prime_list if prime != 0]
    
    
    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""
    
        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)
    
            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452
    
            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1
    
            return dict_counter
    
    
    def divisor_count(num):
        """numの約数の個数を求める"""
        if num < 0:
            return None
        elif num == 1:
            return 1
        else:
            divisor_num = 1
            dict_fact = prime_factorization_2(num)
            for value in dict_fact.values():
                divisor_num *= (value + 1)
            return divisor_num
    
    
    ans=divisor_count(n-1)

    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: # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)
    
        # divisors.sort() # ソートしたけりゃして
        return divisors
    
    l=make_divisors(n)
    def main():
        cnt=0
        for i in l:
            v=n
            while v%i!=0:
                v/=i
            if (v-1)%i==0:
                cnt+=1
        return cnt
    print(ans+main())
            
    
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())


    

    import math
    
    
    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []
    
        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)
    
        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break
    
            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0
    
        return [prime for prime in prime_list if prime != 0]
    
    
    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""
    
        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)
    
            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452
    
            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1
    
            return dict_counter
    
    
    def divisor_count(num):
        """numの約数の個数を求める"""
        if num < 0:
            return None
        elif num == 1:
            return 1
        else:
            divisor_num = 1
            dict_fact = prime_factorization_2(num)
            for value in dict_fact.values():
                divisor_num *= (value + 1)
            return divisor_num
    
    
    ans=divisor_count(n-1)

    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: # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)
    
        # divisors.sort() # ソートしたけりゃして
        return divisors
    
    l=make_divisors(n)
    for i in l:
        v=n
        while v%i!=0:
            v/=i
        if (v-1)%i==0:
            ans+=1
    print(ans)
            
    
resolve()

Submission status: Wrong Answer

Solution code:

def resolve():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                # divisors.append((i, n // i)) # [(1,max), (2, max-1)]
                divisors += [i,n // i]  # [1,2,3,5]
        divisors.sort()
        return divisors

    N = int(input())
    ans = 0

    # K で割り切れない時
    div1 = make_divisors(N-1)
    ans += len(div1) - 1

    # K で割り切れる時
    div2 = make_divisors(N)
    for k in div2:
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n //= k
        if n % k == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

def resolve():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                # divisors.append((i, n // i)) # [(1,max), (2, max-1)]
                divisors += [i,n // i]  # [1,2,3,5]
        divisors.sort()
        return divisors

    N = int(input())
    ans = 0

    # K で割り切れない時
    div1 = make_divisors(N-1)
    ans += len(div1) - 1

    # K で割り切れる時
    div2 = make_divisors(N)
    for k in div2:
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n /= k
        if n % k == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
ns=int(n**0.5)
nms=int((n-1)**0.5)
p=[n]
for i in range(2,ns+1):
  if n%i==0:
    p.append(i)
    if i!=n//i:
      p.append(n//i)

def chd(x,k):
  while x%k==0:
    x=x//k
  return int((x%k)==1)

count=0
for i in p:
  count+=chd(n,i)
for i in range(2,nms+1):
  if (n-1)%i==0:
    count+=1
    if i!=(n-1)//i:
      count+=1
print(count+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
def cd(n):
  ls = []
  for i in range(1,int(n**(1/2))+1):
    if n % i == 0:
      ls += [i, n//i]
  return ls

ans = len(cd(N-1)) - 1
for j in cd(N):
  a = N
  if not j == 1:
    while a % j == 0:
      a //= j    
    if a % j == 1:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
# 約数を列挙　n=10^12までいける
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()
    divisors.remove(1)
    return divisors


def main():
    n = ni()

    ans = set()
    ans.add(n)
    ans.add(n - 1)
    for i in range(2, int(n ** (0.5)) + 1):
        tmp = n
        while tmp % i == 0:
            tmp //= i
        if (tmp - 1) % i == 0:
            ans.add(i)

    yaku = set(make_divisors(n - 1))

    ans = ans | yaku

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
if n == 2:
    print(1)
elif n == 3:
    print(2)
else:
    #print(make_divisors(n-1))
    print(len(make_divisors(n-1))+1)

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
# 約数を列挙　n=10^12までいける
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()
    divisors.remove(1)
    return divisors

def main():
    n = ni()

    ans = set()
    ans.add(n)
    ans.add(n - 1)
    for i in range(2, int(n ** (0.5)) + 1):
        if n % i == 0:
            ans.add(i)
        if  (n % i - 1) % i == 0:
            tmp = 0


    yaku = set(make_divisors(n-1))

    ans = ans | yaku

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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:]

nn=n
d1_2=[]
for i in d1:
  while nn>1:
    nn//=i
  if nn==1:
    d1_2.append(i)
  nn=n
print(len(set(d1_2+d2)))

Submission status: Wrong Answer

Solution code:
N = int(input())
cnt = 0
for i in range(3,int(N**0.5)+1):
    if (N-1)%i==0:
        cnt += 1
print(cnt+1)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
n = int(input())

tmp = n - 1
ret = len(make_divisors(tmp)) - 1

tmplen = make_divisors(tmp)

for item in tmplen:
    if item == 1:
        continue
    val = n
    while True:
        if val % item == 0:
            val = val // item
        else:
            if val % item == 1:
                ret += 1
            break

print(ret)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000)
def joken(a,n):
  if n==1:
    return 1
  elif a%n==0 and a//n>=n:
    return joken(a//n,n)
  elif a%n==1:
    return 1
  else:
    return 0
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
N=int(input())
c=len(make_divisors(N-1))
d=make_divisors(N)
a=0
for i in range(len(d)):
  a+=joken(N,d[i])
print(a+c-1)

Submission status: Wrong Answer

Solution code:
import math
import copy
def prime_factorize(n):
    a = [n]
    for i in range(2, math.floor(n ** 0.5) + 1):
        if n % i == 0:
            a.append(i)
            if n // i != i:
                a.append(n // i)
    return a

N = int(input())
prime_n = prime_factorize(N)
prime_n_1 = prime_factorize(N - 1)

ans = 0
for i in prime_n:
    n = copy.deepcopy(N)
    while (n % i) == 0:
            n = n // i
    if (n % i) == 1:
        ans += 1
ans += len(prime_n_1)
if n > 2:
    print(ans)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
import math
import copy
def prime_factorize(n):
    a = [n]
    for i in range(2, math.floor(n ** 0.5) + 1):
        if n % i == 0:
            a.append(i)
            if n // i != i:
                a.append(n // i)
    return a

N = int(input())
prime_n = prime_factorize(N)
prime_n_1 = prime_factorize(N - 1)

ans = 0
for i in prime_n:
    n = copy.deepcopy(N)
    while (n % i) == 0:
            n = n // i
    if (n % i) == 1:
        ans += 1
ans += len(prime_n_1)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import copy
N = int(input())
ans = 2
for i in range(3, N // 2 + 1):
    if (N % i == 1) | ((N % i == 0) & (N // i == i)) | ((N % i == 0) & ((N // i) % i == 1)):
        ans += 1
if (N // 2 + 1) < N - 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
ans = 1
max_r = math.ceil(n ** 0.5)
for i in range(2, max_r + 1):
    if (n % i == 1) | (n % i == 0) & (n // i > i):
        ans += 1
if max_r < n - 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
"""
0, K, 2K, 3K, 4K, ... = N-1 のとき, 答え.
"""
def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

n = int(input())
themakedivlist = makediv(n-1)
ans = len(themakedivlist)
print(ans+1)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())


def divs(x):
    out = []
    num = 1
    while num < np.sqrt(x):
        if x % num == 0:
            out.append(num)
            if num != x//num:
                out.append(x//num)
        num += 1
    return sorted(out)[1:]


ans = set()


divs_n = divs(n)

for div in divs_n:
    ncp = n
    if (ncp - 1) % div == 0:
        ans.add(div)
        continue
    while ncp % div == 0:
        ncp //= div
        if (ncp-1) % div == 0:
            ans.add(div)
            break


divs_mk = divs(n-1)
for div in divs_mk:
    if div == 1:
        continue
    ans.add(div)

print(len(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())


def divs(x):
    out = []
    num = 1
    while num < np.sqrt(x):
        if x % num == 0:
            out.append(num)
            if num != x//num:
                out.append(x//num)
        if num > 2:
            num += 2
        else:
            num += 1
    return sorted(out)[1:]


ans = set()


divs_n = divs(n)

for div in divs_n:
    ncp = n
    if (ncp - 1) % div == 0:
        ans.add(div)
        continue
    while ncp % div == 0:
        ncp //= div
        if (ncp-1) % div == 0:
            ans.add(div)
            break

# print(divs_n)

divs_mk = divs(n-1)
# print(divs_mk)
for div in divs_mk:
    if div == 1:
        continue
    ans.add(div)

print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())


def factorization(n):
    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


L1 = factorization(N - 1)
s = 1
# print(L1)
for [a, b] in L1:
    s *= (b + 1)
# print(s)


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


for i in set(make_divisors(N))-{1}:
    temp = N
    while temp % i == 0:
        temp //= i
    if (temp-1) % i == 0:
        s += 1
s -= 1
print(s)

Submission status: Wrong Answer

Solution code:
n=int(input())
orgn=n
sidn=n
m=n-1
orgm=m
ncounter=1
mcounter=1
for i in range(2,int(m**0.5)+1):
	if m % i == 0:
		tmpc=1
		m //= i
		while m % i ==0:
			tmpc += 1
			m //= i
		mcounter *= tmpc + 1

if m == orgm:
	mcounter += 1
elif m > int(orgm**0.5):
	mcounter *= 2
mcounter -= 1


for i in range(2,int(n**0.5)+1):
	if orgn % i == 0:
		n = orgn // i
		sidn // i
		while n % i ==0:
			n //= i
		if n % i == 1:
			ncounter += 1
	if sidn % i ==0:
		sidn // i
		while sidn % i ==0:
			sidn //= i


print(ncounter+mcounter)

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int):
    i = 2
    ret = 2
    while i * i <= N:
        tmp = N
        while tmp % i == 0:
            tmp //= i
        tmp %= i
        if tmp == 1:
            ret += 1

        if N % i == 1:
            ret += 1
        i += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()