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:
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)
K_3 = []
count = 0
for k in K_2:
    temp = N
    while temp % k == 0:
        temp //= k
    if temp == 1 or temp % k == 1:
        count += 1
        K_3.append(k)
kk = K_1 + K_3
ans = len(set(kk))
print(ans)

Submission status: Wrong Answer

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)
K_3 = []
count = 0
for k in K_2:
    temp = N
    while temp % k == 0:
        temp //= k
    if temp == 1 or temp % k == 1:
        count += 1
        K_3.append(k)
ans = len(set(K_1 + K_3))
print(ans)

Submission status: Wrong Answer

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)

count = 0
for k in K_2:
    temp = N
    while temp % k == 0:
        temp //= k
    if temp == 1 or temp % k == 1:
        count += 1

ans = count + len(K_1)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt


def divisors(n):
    out = []
    for i in range(1, int(sqrt(n))+1):
        if n % i == 0:
            out.append(i)
            out.append(n//i)

    out.sort()
    return out


n = int(input())
a = len(divisors(n-1)[1:])

d = divisors(n)
for dd in d[1:]:
    nn = n
    while nn % dd == 0:
        nn = nn // dd
    if nn % dd == 1:
        a += 1

print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())

l = []
tmp = n
for i in range(2, int(n**0.5)+1):
    if tmp % i == 0:
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp //= i
        l.append([i, cnt])
if tmp != 1:
    l.append([tmp, 1])
if l == []:
    l.append([n, 1])

cnt = 0
for i in range(1, int((n-1)**0.5)+1):
    if (n - 1) % i == 0:
        if i ** 2 == n - 1:
            cnt += 1
        else:
            cnt += 2

res = cnt
for v, e in l:
    if (n // v ** e) % v == 1:
        res += 1

print(res)

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]

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

divs1 = make_divisors(n - 1)
ans = set(divs1[1:])

for (kk, aa) in factorization(n):
    for i in range(1, aa + 1):
        A = n // (kk ** i)
        if (A - 1) % kk == 0:
            ans.add(kk)

ans.add(n)
print(len(ans))

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]

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

divs1 = make_divisors(n - 1)
ans = set(divs1[1:])

for (kk, aa) in factorization(n):
    for i in range(1, aa + 1):
        A = n // (kk ** i)
    if (A - 1) % kk == 0:
        ans.add(kk)

ans.add(n)
print(len(ans))

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]

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

divs1 = make_divisors(n - 1)
ans = len(divs1)

for (kk, aa) in factorization(n):
    A = n // (kk ** aa)
    if (A - 1) % kk == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:

def check(N,K):
    while N % K == 0:
        N //= K
    return (N % K == 1)

def divisor(N):
    d = []
    K = 2
    while K*K <= N:
        if N % K == 0:
            d.append(K)
            if K*K != N:
                d.append(N//K)
        K += 1
    d.append(N)
    #ans += (N - 1)//K
    return d


N = int(input())

divi = divisor(N)

ans = 0

for x in divi:
    ans += int(check(N,x))

ans += len(divisor(N - 1))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
wnasi = []
for i in range(1, int(pow(N - 1, 0.5)) + 1):
    if (N - 1) % i == 0:
        wnasi.append(i)
        if i != (N - 1) // i:
            wnasi.append((N - 1) // i)
ans += len(wnasi) - 1
wari = []
for i in range(2, int(pow(N, 0.5)) + 1):
    if N % i == 0:
        wari.append(i)
        if i != N // i:
            wari.append(N // i)

for i in wari:
    tmpN = N
    while i < tmpN:
        if tmpN % i == 0:
            tmpN //= i
        else:
            if tmpN % i == 1:
                ans += 1
            break

print(ans + 1)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    max_i = int(math.log2(N))
    div = []
    for i in range(1,int(math.sqrt(N))+1):
        if N % i == 0:
            div.append((i,N//i)); div.append((N//i,i))

    ans = 0
    for a,b in div:
        if a == 1:
            for i in range(1,int(math.sqrt(b-1))+1):
                if b % i == 1:
                    ans += (1 if i*i == b-1 or i == 1 else 2)
        else:
            for i in range(1,max_i+1):
                c = round(math.pow(a,1/i))
                if c ** i == a:
                    if b % c == 1: ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    max_i = int(math.log2(N))
    div = []
    for i in range(1,int(math.sqrt(N))+1):
        if N % i == 0:
            div.append((i,N//i)); div.append((N//i,i))

    ans = 0
    for a,b in div:
        if a == 1:
            for i in range(1,int(math.sqrt(b-1))+1):
                if (b-1) % i == 0:
                    ans += (1 if i*i == b-1 or i == 1 else 2)
        else:
            for i in range(1,max_i+1):
                c = round(math.pow(a,1/i))
                if c ** i == a:
                    if b % c == 1: ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


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


def main():
    input = stdin.buffer.readline
    n = int(input())
    ans = 1
    if n > 2:
        ans += 1
    for i in range(2, int((n - 1) ** 0.5) + 1):
        if (n - 1) % i == 0:
            ans += 2
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if check(n, i):
                ans += 1
            if check(n, n // i):
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


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


def main():
    input = stdin.buffer.readline
    n = int(input())
    ans = 2
    for i in range(2, int((n - 1) ** 0.5) + 1):
        if (n - 1) % i == 0:
            ans += 2
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if check(n, i):
                ans += 1
            if check(n, n // i):
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = set()

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        N //= k

    return False


for k in range(1, int(N**0.5)+10):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        ans.add(k1)
        ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if check(N, k1):
            ans.add(k1)
        if check(N, k2):
            ans.add(k2)

ans.remove(1)
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = set()
for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        if k1>=2:
            ans.add(k1)
        if k2>=2:
            ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if k1>=2:
            v = N // k1
            while v:
                if (v-1)%k1==0:
                    ans.add(k1)
                    break
                if v%k1==0:
                    break
                v //= k1
        if k2>=2:
            v = N // k2
            while v:
                if (v-1)%k2==0:
                    ans.add(k2)
                    break
                if v%k2==0:
                    break
                v //= k2
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = set()
for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        if k1>=2:
            ans.add(k1)
        if k2>=2:
            ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if k1>=2:
            v = N // k1
            while v:
                if (v-1)%k1==0:
                    ans.add(k1)
                    break
                v //= k1
        if k2>=2:
            v = N // k2
            while v:
                if (v-1)%k2==0:
                    ans.add(k2)
                    break
                v //= k2
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = set()
for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        if k1>=2:
            ans.add(k1)
        if k2>=2:
            ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if k1>=2:
            v = N
            while v-1:
                if (v-1)%k1==0:
                    ans.add(k1)
                    break
                v //= k1
        if k2>=2:
            v = N
            while v-1:
                if (v-1)%k2==0:
                    ans.add(k2)
                    break
                v //= k2
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = set()
for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        if k1>=2:
            ans.add(k1)
        if k2>=2:
            ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if k1>=2:
            v = N
            while v:
                if (v-1)%k1==0:
                    ans.add(k1)
                    break
                v //= k1
        if k2>=2:
            v = N
            while v:
                if (v-1)%k2==0:
                    ans.add(k2)
                    break
                v //= k2
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 0
for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        if k1>=2:
            ans += 1
        if k1!=k2 and k2>=2:
            ans += 1
    if N%k==0:
        k1, k2 = k, N//k
        if k1>=2:
            v = N
            while v:
                if (v-1)%k1==0:
                    ans += 1
                    break
                v //= k1
        if k1!=k2 and k2>=2:
            v = N
            while v:
                if (v-1)%k2==0:
                    ans += 1
                    break
                v //= k2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

count = 2
divisor = []

d = 2
while d * d < n - 1:
  if (n - 1) % d == 0:
    count += 2
  d += 1
if d * d == n - 1:
  count += 1

d = 2
while d * d < n:
  if n % d == 0:
    divisor.append(d)
    divisor.append(n // d)
  d += 1
if d * d == n:
  divisor.append(d)

for d in divisor:
  tmp = n
  while tmp % d == 0:
    tmp //= d
  if tmp % d == 1:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

count = 1
divisor = []

d = 2
while d * d < n - 1:
  if n % d == 1:
    count += 2
  d += 1
if d * d == n:
  count += 1

d = 2
while d * d < n:
  if n % d == 0:
    divisor.append(d)
    divisor.append(n // d)
  d += 1
if d * d == n:
  divisor.append(d)
count += 1

for d in divisor:
  tmp = n
  while tmp % d == 0:
    tmp //= d
  if tmp % d == 1:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

count = 1
divisor = []

d = 2
while d * d < n - 1:
  if n % d == 1:
    count += 2
  d += 1
if d * d == n:
  count += 1

d = 2
while d * d < n:
  if n % d == 0:
    divisor.append(d)
    divisor.append(n // d)
  d += 1
if d * d == n:
  divisor.append(d)
count += 1

for d in divisor:
  tmp = n
  while tmp % d == 0:
    tmp //= d
  if tmp % d == 1:
    count += 1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()

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

def Base_10_to_n(X, n):
  if (int(X/n)):
     return Base_10_to_n(int(X/n), n)+" "+str(X%n)
  return " "+str(X%n)

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

d = make_divisors(N)+make_divisors(N-1)



ans = 0
for x in d:
  l = list(Base_10_to_n(N, x).strip())
  for i in l[::-1]:
    if i == "0" or i ==" ":
      continue
    else:
      if i == "1":
        ans += 1
        break
      else:
        break

print(ans+2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()

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

def Base_10_to_n(X, n):
  if (int(X/n)):
     return Base_10_to_n(int(X/n), n)+" "+str(X%n)
  return " "+str(X%n)

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

d = make_divisors(N)+make_divisors(N-1)



ans = 0
for x in d:
  l = list(Base_10_to_n(N, x).strip())
  for i in l[::-1]:
    if i == "0":
      continue
    else:
      if i == "1":
        ans += 1
      else:
        break

print(ans+2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()

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

def Base_10_to_n(X, n):
  if (int(X/n)):
     return Base_10_to_n(int(X/n), n)+" "+str(X%n)
  return " "+str(X%n)

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

d = make_divisors(N)+make_divisors(N-1)

ans = 0
for x in d:
  l = list(Base_10_to_n(N, x).strip(" 0"))
  if l[-1] == "1":
    ans += 1

print(ans+2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()

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

def Base_10_to_n(X, n):
  if (int(X/n)):
     return Base_10_to_n(int(X/n), n)+" "+str(X%n)
  return " "+str(X%n)

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

d = make_divisors(N)

ans = 1
for x in d:
  l = list(Base_10_to_n(N, x).strip(" 0"))
  if l[-1] == "1":
    ans += 1

dic = factorization(N-1)
P = [k for k in dic]

tempans = 1
for p,n in P:
  tempans *= n+1
ans += tempans-1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()

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

dic = factorization(N)

P = [k for k in dic]

def Base_10_to_n(X, n):
  if (int(X/n)):
     return Base_10_to_n(int(X/n), n)+" "+str(X%n)
  return " "+str(X%n)

ans = 1
if not (len(dic) == 1 and dic[0][1] == 1):
  for p,n in P:
    l = list(Base_10_to_n(N, p).strip(" 0"))
    if l[-1] == "1":
      ans += 1
else:
  ans = 1


dic = factorization(N-1)
P = [k for k in dic]

tempans = 1
for p,n in P:
  tempans *= n+1
ans += tempans-1

print(ans)