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())
if n == 2:
    print(1)
    exit()
ans = []
divisors = []
for i in range(2,int(n**0.5)+1):
    #n-1の約数は全部
    if (n-1) % i == 0:
        ans.append(i)
        if i != (n-1) // i:
            ans.append((n-1)//i)
    #nの約数はやってみる
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n//i)
for item in divisors:
    num = n
    while num%item == 0:
        num = num//item
    if num%item == 1:
        ans.append(item)
print(divisors)
print(ans)
print(len(ans)+2)#k=n,n-1がはいっていないので+2

'''
import math
n = int(input())
ans = []
divisors = []

for i in range(2,math.ceil(n**0.5)+1):
    num = n
    while num >= i:
        if num%i == 0:
            num //= i
        else:
            num -= i
    print(num)
    if num == 1:
        ans.append(i)
    if n % i == 0:
        divisors.append(i+1)
        if i != n // i:
            divisors.append(n//i+1)

print(ans)
print(divisors)
print(len(ans)+len(divisors))

#[2, 3, 4, 5, 10, 20, 157, 314, 628, 785, 1570, 3140, 3141]
'''

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = []
divisors = []
for i in range(2,int(n**0.5)+1):
    #n-1の約数は全部
    if (n-1) % i == 0:
        ans.append(i)
        if i != (n-1) // i:
            ans.append((n-1)//i)
    #nの約数はやってみる
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n//i)
for item in divisors:
    num = n
    while num%item == 0:
        num = num//item
    if num%item == 1:
        ans.append(item)
#print(divisors)
#print(ans)
print(len(ans)+2)#k=n,n-1がはいっていないので+2

'''
import math
n = int(input())
ans = []
divisors = []

for i in range(2,math.ceil(n**0.5)+1):
    num = n
    while num >= i:
        if num%i == 0:
            num //= i
        else:
            num -= i
    print(num)
    if num == 1:
        ans.append(i)
    if n % i == 0:
        divisors.append(i+1)
        if i != n // i:
            divisors.append(n//i+1)

print(ans)
print(divisors)
print(len(ans)+len(divisors))

#[2, 3, 4, 5, 10, 20, 157, 314, 628, 785, 1570, 3140, 3141]
'''

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())


# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


div_n = divisor(N)
div_n1 = divisor(N - 1)

ans = []
for d in div_n:
    nd = N // d
    if nd % d == 1 or nd % d == 0:
        ans.append(d)

for d in div_n1:
    ans.append(d)


ans = list(set(ans))
# print(ans)
print(len(ans)-1)

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())


# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


div_n = divisor(N)
div_n1 = divisor(N - 1)

ans = []
for d in div_n:
    nd = N // d
    if nd % d == 1:
        ans.append(d)

for d in div_n1:
    ans.append(d)


ans = list(set(ans))
# print(ans)
print(len(ans)-1)

Submission status: Wrong Answer

Solution code:
# 約数を全列挙する関数
def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors


N = int(input())
ans = 0
K_cand = set(make_divisors(N) + make_divisors(N-1))  # N = K^a (bK + 1) と表現できるので K は N or N-1 の約数であることが必要

for K in K_cand:
    if K == 1:  # K = 1 を除外
        continue

    # 割れるだけ割る
    while N%K == 0:
        N = N // K

    # 引けるだけ引く
    N = N%K

    # 判定
    if N == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())


# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


div_n = divisor(N)
div_n1 = divisor(N - 1)

ans = []
for d in div_n:
    nd = N // d
    if nd % d == 1:
        ans.append(d)

for d in div_n1:
    ans.append(d)


ans = list(set(ans))
print(ans)
print(len(ans)-1)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 1
a = list(set(prime_factorize(n)))
b = collections.Counter(prime_factorize(n-1))
for i in b.values():
    ans *= (i+1)
if len(a) == 1:
    ans += 1
for i in range(len(a)):
    for j in range(i):
        if a[i]%a[j] == 1:
            ans += 1
        
if n == 2:
    ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
nn=n-1
ans=set([nn])
for i in range(2,int(nn**0.5)+1):
  if nn%i==0:
    ans.add(i)
    ans.add(nn//i)
l=[n]
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    l.append(i)
    l.append(n//i)
for j in l:
  m=n
  while m%j==0:
    m//=j
  if m%j==1:
    ans.add(j)
print(len(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
def check(x,m):
    if m % x == 0:
        return check(x,m//x)
    else:
        return m % x == 1

def count(n):
    cnt = 1
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0:
            cnt += 2
    return cnt

def count2(n):
    cnt = 1
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            if check(i,n):
                cnt += 1
            if check(n//i,n):
                cnt += 1
    return cnt

ans = count(n-1)
ans += count2(n)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 1
a = list(set(prime_factorize(n)))
b = collections.Counter(prime_factorize(n-1))
for i in b.values():
    ans *= (i+1)
if a == [2]:
    ans += 1
for i in range(len(a)):
    for j in range(i):
        if a[i]%a[j] == 1:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
nn=n-1
ans=set([nn])
for i in range(2,int(nn*0.5)+1):
  if nn%i==0:
    ans.add(i)
    ans.add(nn//i)
l=[n]
for i in range(2,int(nn*0.5)+1):
  if n%i==0:
    l.append(i)
    l.append(n//i)
for j in l:
  m=n
  while m%j==0:
    m//=j
  if m%j==1:
    ans.add(j)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import math
INT_MAX=10**18+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
#################################################################################
n=int(input())
def calc(x,n):
    while(n%x==0):
        n//=x
    if n%x==1:
        return True
    else:
        return False

def factors(n):
    A=[]
    i=1
    while(i<=math.sqrt(n)):
        if n%i==0:
            if (n//i)==i:
                A.append(i)
            else:
                A.append(i)
                A.append(n//i)
        i+=1
    return A
x=len(factors(n-1))-1
#print(x)
A=factors(n)
A.sort()
#print(A)
for i in range(1,len(A)-2):
    if calc(A[i],n) is True:
        x+=1
print(x+1)

Submission status: Wrong Answer

Solution code:
import math
INT_MAX=10**18+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
#################################################################################
n=int(input())
def calc(x,n):
    #print(n//x)
    if ((n//x)%x)==0 or ((n//x)-x==1) or (n//x)%x==1:
        return True
    else:
        return False

def factors(n):
    A=[]
    i=1
    while(i<=math.sqrt(n)):
        if n%i==0:
            if (n//i)==i:
                A.append(i)
            else:
                A.append(i)
                A.append(n//i)
        i+=1
    return A
x=len(factors(n-1))-1
#print(x)
A=factors(n)
A.sort()
#print(A)
for i in range(len(A)//2):
    if calc(A[i],n) is True:
        x+=1
print(x)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1###int(N**(1/2))+1以上についてカウント
###あらかじめK=Nはカウント

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        ###
        #print(i,(N-1)//i)
        ###

if int((N-1)**(1/2)) == (N-1)**(1/2):
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and N**(1/m) == int(N**(1/m)):###m=1のときはK=Nの話なのでpass
        Klist[int(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1
###
#print("count",count)
#print(Klist)
###
print(sum(Klist)+count-Klist[1])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
c = 0

for i in range(2,int(N**0.5)+1):
    if N % i == 0:
        A.append(i)
        A.append(N//i)

for i in range(2,int((N-1)**0.5)+1):
    if (N - 1) % i == 0:
        A.append(i)
        A.append((N-1)//i)

if N == 2:
    print(2)
else:
    for i in A:
        start = N
        while(True):
            if start % i != 0:
                break
            start = start//i
        if start % i == 1:
            c += 1
    print(c+2)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
 
m = n-1
ans1 = 0
for i in range(1, math.ceil(math.sqrt(m))):
  if m%i == 0:
    ans1 += 2
if m % math.ceil(math.sqrt(m)) == 0:
  ans1 += 1
ans1 -= 1

ans2 = 0
for i in range(2, math.ceil(math.sqrt(n))):
  if n%i == 0:
    k = n
    while k % i == 0:
      k = k // i
    if k % i == 1:
      ans2 += 1
    k = n
    j = n/i
    while k % j == 0:
      k = k // j
    if k % j == 1:
      ans2 += 1
      
if n % math.ceil(math.sqrt(n)) == 0:
  ans2 += 1
ans2 += 1
#print(ans1, ans2)
print(ans1+ans2)

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-

#約数列挙（ググってでてきたやつ）
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#入力
N_given = int(input())

#見つけたKのリスト
list_found_K = []


#パターン1 
divisors_N_minus_1 = make_divisors(N_given-1)
#みつけたKを追加
for divs in divisors_N_minus_1:
	if divs != 1:
		list_found_K.append(divs)

#パターン2
#K候補（Nの約数）
divisors_N = make_divisors(N_given)
divisors_N.remove(1)

#見つかっているものは除外
#しようかと思いましたがNとN-1が互いに素であることは自明でした	

#全てのN候補で試行
for candidate_K in divisors_N:
	N_wk = N_given
	#Kで割り尽くす
	while N_wk % candidate_K == 0:
		N_wk //=candidate_K

	#パターン1風　1引いてK候補で割れたらKに正式採用
	if (N_wk-1) % candidate_K == 0:
		list_found_K.append(candidate_K)

print(list_found_K)
print(len(list_found_K))

Submission status: Wrong Answer

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

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

L = collections.Counter(prime_factorize(N-1))

A = 1
for i,v in L.items():
    A *= (v+1)


c = collections.Counter(prime_factorize(N))

for k,v in c.items():
    tar = N /(k**v)
    for i in range(v):
        b = tar % (k**(i+1))

        if b == 1:
            A += 1

print(A)

Submission status: Wrong Answer

Solution code:

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

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

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


def resolve():
    N = int(input())
    ys= set(make_divisors(N))
    ys2= set(make_divisors(N-1))

    ys3 = ys & ys2

    for i in ys3:
        ys2.remove(i)
    x =set([i for i in ys if check(N,i)])

    print(len(x | ys2))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def judge(n, k):
    n_ = n
    while n_ % k == 0:
        n_ = n_ // k
    return n_ % k == 1


n = int(input())
if n == 2:
    print(1)
    exit()
cnt = 0
for k in range(2, -int(-n**0.5)+1):
    if n % k == 0:
        if judge(n, k):
            cnt += 1
        if judge(n, n//k):
            cnt += 1
    if (n-1) % k == 0:
        if judge(n, k):
            cnt += 1
        if judge(n, (n-1)//k):
            cnt += 1
print(cnt+2)

Submission status: Wrong Answer

Solution code:
def check(i):
	local = k
	other = (local//i)
	pw=0
	while(local%i==0):
		local//=i
		pw+=1
	if(local%i==1):
		yo = local//i
		if(yo>=2 and yo<=k):
			local = k
			while(local%yo==0):
				local//=yo
			if(local%yo==1):
				setl.add(yo)
		setl.add(i)
	pw=0; i=other; local=k
	if(other<2 or other>k):
		return
	while(local%i==0):
		local//=i
		pw+=1
	if(local%i==1):
		setl.add(i)
import math
k=int(input())
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
print(len(setl))

Submission status: Wrong Answer

Solution code:
def judge(n, k):
    n_ = n
    while n_ % k == 0:
        n_ = n_ // k
    return n_ % k == 1


n = int(input())
if n == 2:
    print(1)
    exit()
cnt = 0
for k in range(2, -int(-n**0.5)):
    if n % k == 0:
        if judge(n, k):
            cnt += 1
        if judge(n, n//k):
            cnt += 1
    if (n-1) % k == 0:
        if judge(n, k):
            cnt += 1
        if judge(n, (n-1)//k):
            cnt += 1
print(cnt+2)

Submission status: Wrong Answer

Solution code:
def f_division_or_substraction():
    N = int(input())

    def divisor_list(n):
        """n の正の約数のリスト"""
        ret = set()
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                ret.update({k, n // k})
        return sorted(ret)

    ans = (len(divisor_list(N - 1)) - 1)  # K >= 2 なので、-1 する
    for k in divisor_list(N):
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n //= k
        ans += 1
    return ans

print(f_division_or_substraction())

Submission status: Wrong Answer

Solution code:
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
  
n = int(input())
a = factorization(n)
ans = 1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      cnt = 0
      cnt += a[i][1]-a[i][1]%j
      #print(a[i][0]**j,cnt,n/(a[i][0]**cnt),n/(a[i][0]**cnt) % (a[i][0]**(j)))
      if n/(a[i][0]**cnt) % (a[i][0]**(j)) == 1:
            ans += 1
if len(a) == 1:
  ans -= 1
if n == 2:
  ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:
def f_division_or_substraction():
    N = int(input())

    def divisor_list(n):
        """n の正の約数のリスト"""
        ret = set()
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                ret.update({k, n // k})
        return sorted(ret)

    ans = (len(divisor_list(N - 1)) - 1)  # K >= 2 なので、-1 する
    for k in divisor_list(N):
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n //= k
        ans += 1

print(f_division_or_substraction())

Submission status: Wrong Answer

Solution code:
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
  
n = int(input())
a = factorization(n)
ans = 1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      cnt = 0
      cnt += a[i][1]-a[i][1]%j
      #print(a[i][0]**j,cnt,n/(a[i][0]**cnt),n/(a[i][0]**cnt) % (a[i][0]**(j)))
      if n/(a[i][0]**cnt) % (a[i][0]**(j)) == 1:
            ans += 1
if len(a) == 1:
  ans -= 1
if n == 2:
  ans = 1

Submission status: Wrong Answer

Solution code:
n = int(input())


def factorization(n):
    retval = []
    tmp = n
    for i in range(2, int(-(-n**.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            retval.append((i, cnt))
    if tmp != 1:
        retval.append((tmp, 1))
    if not retval:
        retval.append((n, 1))
    return retval


ans = 1
for k, v in factorization(n-1):
    ans *= (v+1)
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
 
m = n-1
ans1 = 0
for i in range(1, int(math.sqrt(m))):
  if m%i == 0:
    ans1 += 2
if m % int(math.sqrt(m)) == 0:
  ans1 += 1

ans2 = 0
for i in range(2, int(math.sqrt(n))):
  if n%i == 0:
    k = n
    while k % i == 0:
      k = k // i
    if k % i == 1:
      ans2 += 1
    k = n
    j = n/i
    while k % j == 0:
      k = k // j
    if k % j == 1:
      ans2 += 1
      
if n % int(math.sqrt(n)) == 0:
    k = n
    while k % int(math.sqrt(n)) == 0:
      k = k // int(math.sqrt(n))
    if k % int(math.sqrt(n)) == 1:
      ans2 += 1
print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
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
  
n = int(input())
a = factorization(n)
ans = 1
if n == 2:
  print(1)
  exit()
  
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      cnt = 0
      cnt += a[i][1]-a[i][1]%j
      print(a[i][0]**j,cnt,n/(a[i][0]**cnt),n/(a[i][0]**cnt) % (a[i][0]**(j)))
      if n/(a[i][0]**cnt) % (a[i][0]**(j)) == 1:
            ans += 1
if len(a) == 1:
  ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
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
n = int(input())
a = factorization(n)
ans = 1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      cnt = 0
      cnt += a[i][1]-a[i][1]%j
      #print(a[i][0]**j,cnt,n/(a[i][0]**cnt),n/(a[i][0]**cnt) % (a[i][0]**(j)))
      if n/(a[i][0]**cnt) % (a[i][0]**(j)) == 1:
            ans += 1
if len(a) == 1:
  ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
 
m = n-1
ans1 = 0
for i in range(1, int(math.sqrt(m)+1)):
  if m%i == 0:
    ans1 += 2

ans2 = 0
for i in range(2, int(math.sqrt(n)+1)):
  if n%i == 0:
    k = n
    while k % i == 0:
      k = k // i
    if k % i == 1:
      ans2 += 1
    k = n
    j = n/i
    while k % j == 0:
      k = k // j
    if k % j == 1:
      ans2 += 1
print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
def check(i):
	local = k
	other = (local//i)
	pw=0
	while(local%i==0):
		local//=i
		pw+=1
	if(local==1 or local%i==1):
		setl.add(i)
	pw=0; i=other; local=k
	if(other<2 or other>k):
		return
	while(local%i==0):
		local//=i
		pw+=1
	if(local==1 or local%i==1):
		setl.add(i)
import math
k=int(input())
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
print(len(setl))

Submission status: Wrong Answer

Solution code:
import math
K = int(input())
ans = 2
sq = math.ceil(math.sqrt(K))

yakusu = []
for i in range(2, sq):
    if (K - 1) % i == 0:
        if i * i == (K - 1):
            ans += 1
        else:
            ans += 2
    if  K % i == 0:
        tmp = K
        while True:
            if tmp % i != 0:
                break
            tmp = tmp / i
        if tmp % i == 1:
            ans += 1
        
        if i * i != K:
            tmp = K
            i2 = K / i
            while  True:
                if tmp % i2 != 0:
                    break
                tmp = tmp / i2
            if tmp % i2 == 1:
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 1
b = collections.Counter(prime_factorize(n-1))
for i in b.values():
    ans *= (i+1)
print(ans + 1)

Submission status: Wrong Answer

Solution code:
def check(i):
	local = k
	other = (local//i)
	pw=0
	while(local%i==0):
		local//=i
		pw+=1
	if(local==1 or local%i==1):
		setl.add(i)
	pw=0; i=other; local=k
	if(other<2 or other>k):
		return
	while(local%i==0):
		local//=i
		pw+=1
	if(local==1 or local%i==1):
		setl.add(i)
import math
k=int(input())
setl = set()
setl.add(k); setl.add(k-1)
for i in range(2,int(math.sqrt(k))+1):
	check(i)
print(len(setl))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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

    # divisors.sort()
    return divisors

n = onem()
co = 0

nnn = make_divisors(n)

mp = make_divisors(n-1)


for i in nnn:
    nn = n
    if i == 1:
        co += 1
        continue
    while True:
        if nn == 1:
            co += 1
            break
        elif nn <= 0:
            break
        if nn % i:
            nn = nn % i if nn//i else 0
        else:
            nn //= i
for i in mp:
    if i != 1 and i != n-1:
        co += 1
print(co)

Submission status: Wrong Answer

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

m = n-1
ans1 = 0
for i in range(2, int(math.sqrt(m))):
  if m%i == 0:
    ans1 += 2

ans2 = 0
for i in range(2, int(math.sqrt(n))):
  if n%i == 0:
    k = n
    while k % i == 0:
      k = k // i
    if k % i == 1:
      ans2 += 1
    k = n
    j = n/i
    while k % j == 0:
      k = k // j
    if k % j == 1:
      ans2 += 1
print(ans1+ans2)

Submission status: Wrong Answer

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

from sys import stdin


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


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

        if N == 1:
            return True
    return False


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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
n = int(input())
a = factorization(n)
ans = 1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
if len(a) >= 2:
  for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      cnt = 0
      cnt += a[i][1]-a[i][1]%j
      #print(a[i][0]**j,cnt,n/(a[i][0]**cnt),n/(a[i][0]**cnt) % (a[i][0]**(j)))
      if n/(a[i][0]**cnt) % (a[i][0]**(j)) == 1:
            ans += 1
if n == 2:
  ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import sqrt
input = stdin.readline

N = int(input())

s = set([N - 1, N])


for i in range(2, int(sqrt(N)) + 1):
    tmp = N
    if (tmp - 1) % i == 0:
        s.add(i)
        s.add((tmp - 1) // i)
    elif tmp % i == 0:
        while tmp % i == 0:
            tmp //= i

        if tmp % i == 1:
            s.add(i)

        tmp = N
        while tmp % (N // i) == 0:
            tmp //= (N // i)

        if tmp % (N // i) == 1:
            s.add(N // i)

# print(s)
print(len(s))

Submission status: Wrong Answer

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

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

N=int(input())
ans=len(make_divisors(N-1))

lst=prime_factorize(N)
l=len(lst)
cnt=1
for i in range(1,l):
    if lst[i]==lst[i-1]:
        cnt+=1
        continue
    else:
        num=lst[i-1]
        kkk=N//(num**cnt)
        if kkk%num==1:
            ans+=1
        cnt=1
num=lst[-1]
kkk=N//(num**cnt)
if kkk%num==1:
    ans+=1

if lst[0]==lst[-1]:
    num=len(lst)
    ans+=len(make_divisors(num))
    
print(ans)

Submission status: Wrong Answer

Solution code:
def check(i):
	local = k
	other = (local//i)
	pw=0
	while(local%i==0):
		local//=i
		pw+=1
	if(local==1 or local%i==1):
		setl.add(i)
	pw=0; i=other; local=k
	while(local%i==0):
		local//=i
		pw+=1
	if(local==1 or local%i==1):
		setl.add(i)
import math
k=int(input())
setl = set()
setl.add(k); setl.add(k-1)
for i in range(2,int(math.sqrt(k))+1):
	check(i)
print(len(setl))

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())



def grot(x,y):
  while x>=y and x%y==0:
    x=x//y
  else:
    x=x-x//y*y
    if x<y:
      if x==1:return 1
      else: return 0  

sum=0
for i in range(2,n//2):
  sum+= grot(n,i)

print(sum+2)

Submission status: Wrong Answer

Solution code:
N = int(input())

divisor = set([N, N - 1])
x = N
for i in range(2, int(x ** 0.5) + 1):
    z = x
    while z % i == 0:
        z //= i
    if z % i == 1:
        divisor.add(i)
        
    if i == x // i:
        continue
        
    z = x
    while z % (x // i) == 0:
        z //= (x // i)
    if z % (x // i) == 1:
        divisor.add((x // i))
        
x = N - 1
for i in range(2, int(x ** 0.5) + 1):
    if x % i == 0:
        divisor.add(i)
        divisor.add(x // i)

print(len(divisor))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import sqrt
input = stdin.readline

N = int(input())

s = set([N - 1, N])


for i in range(2, int(sqrt(N)) + 1):
    tmp = N
    if (tmp - 1) % i == 0:
        s.add(i)
        s.add((tmp - 1) // i)
    elif tmp % i == 0:
        while tmp % i == 0:
            tmp //= i

        if tmp % i == 1:
            s.add(i)

        tmp = N
        while tmp % (N // i) == 0:
            tmp //= (N // i)

        if tmp % (N // i) == 1:
            s.add(tmp // i)

# print(s)
print(len(s))