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

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

def sousa(n, k):
    while n >= k:
        if n % k == 0:
            n = n // k
        else:
            n = n % k
    return n

N = int(input())
cnt = 0

divisors = make_divisors(N)
for i in divisors:
    if i == 1: continue
    if sousa(N, i) == 1:
        cnt += 1

lst = factorization(N-1)
tuika = 1
for i in range(len(lst)):
    tuika *= lst[i][1]+1
# cnt += len(make_divisors(N-1))-1
cnt += tuika-1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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 = set()

a = prime_factorize(n)

from collections import Counter

c = Counter(a)

for i in c.keys():
    tmp = 1
    for j in c.keys():
        if j != i:
            tmp *= pow(j, c[j])
    if (tmp - 1) % i == 0:
        ans.add(i)

#約数の列挙
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

d = make_divisors(n - 1)

for i in d:
    if i != 1:
        ans.add(i)

ans.add(n)

if len(c) == 1:
    j = c.keys()
    for k in j:
        ans.add(k)

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

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

N = int(input())

def chk(K):
    n = N
    while n >= K:
        if n%K:
            n %= K
        else:
            n //= K
    if n == 1:
        return True
    else:
        return False

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

for i in range(2, int(N**0.5)+1):
    if N%i==0:
        if chk(i):
            ans.add(i)
        # j = N//i
        # if chk(j):
        #     ans.add(j)
    if (N-1)%i==0:
        # if chk(i):
        ans.add(i)
        j = (N-1)//i
        # if chk(j):
        ans.add(j)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())

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

    # divisors.sort()
    return divisors



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

def check(i, k):
    if i == 1:
        return True
    if i < 1:
        return False
    if i % k == 0:
        return check(i // k, k)
    else:
        p = sum([int(a) for a in list(str(i))])
        if p % k == 1:
            return True
        else:
            return False
k = 3
while k < n:
    if check(n, k):
        ansl.append(k)
    k *= 3
ansl.append(2)
ansl.append(n)
print(len(set(ansl)))

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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())
soin=factorization(n)
minus=factorization(n-1)
# print(soin)
# print(minus)
d={}
for i in range(len(soin)):
    d[soin[i][0]]=soin[i][1]
# print(d)
ans=0
tmp=1
for i in range(len(minus)):
    if minus[i][0]!=1:
        tmp*=minus[i][1]+1
tmp-=1
ans+=tmp
print(ans)

# for i in range(len(soin)):
#     lst=factorization(soin[i][0]-1)
#     for j in lst:
#         if lst[0]

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial as fact
n = int(input())
cnt = 0
p = {}
tmp = n - 1

for i in range(2, int(n**0.5)+1):
  if tmp % i == 0:
    while tmp % i == 0:
      tmp //= i
      p[i] = p.get(i, 0) + 1
if tmp != 1:
  p[i] = p.get(tmp, 0) + 1
ans = 1
for pp in p.values():
  ans *= pp + 1
print(ans + 1)

Submission status: Wrong Answer

Solution code:
"""
NTC here
"""
import sys
inp = sys.stdin.readline
def input(): return inp().strip()
# flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)
 
def iin(): return int(input())
 
 
def lin(): return list(map(int, input().split()))
 
 
# range = xrange
# input = raw_input
 
def main():
    T = 1
    while T:
        T-=1
        n = iin()
        ans = set()
        ans.add(n)
        def check1(x):
            n1 = x-1
            i = 1
            while i*i<=n1:
                if n1%i==0:
                    if i>=2:ans.add(i)
                    ans.add(n1//i)
                i+=1
        def check2(x):
            n1 = n
            while n1>=x:
                if n1%x==0:
                    n1//=x
                else:
                    n1 = n1%x
            if n1==1:
                ans.add(x) 
        check1(n)
        i = 2
        while i*i<=n:
            if n%i==0:
                check2(i)
                if i!=n//i:
                    check2(n//i)
            i+=1
        print(len(ans))
        # print(ans)






 
 
 
 
main()
 
# threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = [n,n-1]
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
ass = prime_factor(n)
for i in range(2, int(n**0.5)+1):
    if i not in ass:
        if n%i == 1:
            ans.append(i)
            ans.append((n-1)//i)
    else:
        temp = 1
        for j in range(len(ass)):
            if ass[j] != i:
                temp *= ass[j]
        if temp%i == 1:
            ans.append(i)
set(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ans = 0
    for i in range(2,int(n**0.5) + 1):
        var = n
        while not var%i:
            var = var // i
        if var%i == 1:
            ans += 1
            if var == n:
                ans += 1
    print(ans + 2)

main()

Submission status: Wrong Answer

Solution code:
import math

n = int(input())

b = []
l = []

a = set()
a.add(n)
a.add(n-1)
ans = 2

for i in range(1, math.ceil(n ** 0.5)):
    if n % i == 0:
        l.append([n//i, i])
    elif (n - 1) % i == 0:
        b.append([(n - 1) // i, i])
        a.add((n - 1) // i)
        a.add(i)

ans += len(b) * 2

for x, y in l[1:]:
    while True:
        if x % y == 0:
            x //= y
        else:
            if x % y == 1:
                a.add(y)
            break
        


print(len(a))

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
def countfact(n,rem):
    if n!=1:
        for i in range(2,int(math.sqrt(n))+2):
            if n%i==0:
                a,b=n//i,i
                #print(a,'fac1',b,'fac2')
                if a!=1:
                    rem.add(a)
                if b!=1:
                    rem.add(b)
n=int(sys.stdin.readline())
count=0
temp=n
rem=set()
rem.add(n-1)
vis=defaultdict(int)
countfact(n-1,rem)
for i in rem:
    vis[i]=1

vis[1]=1
for i in range(2,int(math.sqrt(n))+2):
    if n%i==0:
        a,b=n//i,i
        c=0
        if b>a and vis[a]==0:
            vis[a]=1
            while a%1==0 and b>a:
                
                #print(a,'before')
                if b%a==1:
                    c+=1
                a=math.sqrt(a)
                #print(a,'a')
        elif vis[b]==0:
            vis[b]=1
            while b%1==0 and a>b:
                #print(b,'before')
               
                if a%b==1:
                    c+=1
                b=math.sqrt(b)
                #vis[b]=1
                #print(b,'after')
        count+=c
        #countfact(b-1,rem)
#print(count,'count')       
ans=len(rem)+count
if 1 in rem:
    ans-=1
#print(rem,'rem')
#print(ans,'ans')
count,z=1,True
while z:
    a=math.sqrt(n)
    #print(a,'a')
    if a%1==0 and vis[a]==0:
        count+=1
    else:
        z=False
    n=a
print(ans+count)

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

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

def sousa(n, k):
    while n >= k:
        if n % k == 0:
            n = n // k
        else:
            n = n - k
    return n

N = int(input())
cnt = 0

divisors = make_divisors(N)
for i in divisors:
    if i == 1: continue
    if sousa(N, i) == 1:
        cnt += 1

lst = factorization(N-1)
tuika = 1
for i in range(len(lst)):
    tuika *= lst[i][1]+1
# cnt += len(make_divisors(N-1))-1
cnt += tuika-1
print(cnt)

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

if N == 2:
    print("1")
else:

    hoge = make_divisors(N - 1)
    hoge.append(N)
    X = make_divisors(N)

    for i in range(1,len(X)):
        a = X[i]
        while a <= N:
            
            if (N // a) % X[i] == 1:
                hoge.append(X[i])
            a *= X[i]

    print(len(set(hoge))-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = [n,n-1]
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
ass = prime_factor(n)
for i in range(2, int(n**0.5)+1):
    if i not in ass:
        if n%i == 1:
            ans.append(i)
            ans.append((n-1)//i)
    else:
        temp = 1
        for j in range(len(ass)):
            if ass[j] != i:
                temp *= ass[j]
        if temp%i == 1:
            ans.append(i)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())

n1 = N - 1

n1_count = 1

i = 2
while i * i <= n1:
    if n1 % i == 0:
        if n1 // i != i:
            n1_count += 2
        else:
            n1_count += 1
    
    i += 1

n_count = 1
i = 2
while i * i <= N:
    if N % i == 0:
        a = i
        n = N
        while n % a == 0:
            n = n // a
        if (n - 1) % a == 0:
            n_count += 1
        
        if N // i != i:
            a = N // i
            n = N
            while n % a == 0:
                n = n // a
            if (n - 1) % a == 0:
                n_count += 1

    i += 1

print(n1_count + n_count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def MI():return map(int,input().split())
def LI():return list(MI())

# n,k,c=MI()
# s=input()

"""nを素因数分解"""
"""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

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

n=int(input())
l=[]

soinsuu=(factorization(n-1))
yakusuu=(make_divisors(n-1))
#[[2, 1], [3, 2], [5, 1], [349, 1]]
# print(yakusuu)
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1


for k in range(2,50+1):
    NN=int(n)
    while NN>=k:
        if NN%k==0:
            NN=NN//k
        else:
            NN=NN%k
    if NN==1:
        l+=k,
    # if NN%k==1:
    #     l+=k,
ll=(l+yakusuu+[n])
if n%2==0:
    ll+=2,
print(len(set(ll)))#,ll)

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())
nl = make_divisors(n)
nl_p = make_divisors(n+1)
nl_m = make_divisors(n-1)
l = sorted(list(set(nl + nl_p+nl_m)))

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

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
res = 1


n = 10 ** 6 + 5
fl = [1] * n
fl[0] = 0
fl[1] = 0
lprime = []
for i in range(n):
    if fl[i] == 1:
        lprime.append(i)
        ti = i * 2
        while ti < n:
            fl[ti] = 0
            ti += i


def prime_factorize(n):
    global lprime
    a = []
    for p in lprime:
        if p * p > n:
            break
        while n % p == 0:
            a.append(p)
            n //= p
    if n != 1:
        a.append(n)
    return a


tres = prime_factorize(N - 1)
ctres = collections.Counter(tres)
for s in ctres.values():
    res *= s + 1

tres = prime_factorize(N)
ctres = collections.Counter(tres)
for c in ctres.keys():
    t = N
    while t % c == 0:
        t /= c
    if (t - 1) // c == 0:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
#x
x=int(input())

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

    # divisors.sort()
    return divisors

ans = make_divisors(x-1)
ans2 = len(ans) + 1

print(ans2)

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())
k1 = make_divisors(N)
k2 = make_divisors(N-1)
ans = 0
n = N
print(k1,k2)
for x in k1:
    
    if x == 1:continue
    if n%x == 1:ans+=1
    while n%x == 0:
        n//=x
        if n%x == 1:
            ans+=1
            print(x)
    n = N
for x in k2:
    if x == 1:continue
    if n%x == 1:ans+=1
    while n%x == 0:
        n//=x
        if n%x == 1:
            ans+=1
            print(x)
    n = N
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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 = set()

a = prime_factorize(n)

from collections import Counter

c = Counter(a)

for i in c.keys():
    tmp = 1
    for j in c.keys():
        if j != i:
            tmp *= pow(j, c[j])
    if (tmp - 1) % i == 0:
        ans.add(i)

#約数の列挙
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

d = make_divisors(n - 1)

for i in d:
    if i != 1:
        ans.add(i)

ans.add(n)

if len(c) == 1:
    d = make_divisors(n)
    for i in d:
        if i != 1:
            ans.add(i)

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

Submission status: Wrong Answer

Solution code:
## F
import numpy as np

def check_primary(n):
    Is_Primary=True
    for j in range(2,int(n**0.5)+2):
        if n%j==0:
            Is_Primary=False
            break
    if n==2:
        Is_Primary=True
    return Is_Primary

def find_primary(n):
    primaries=[]
    for i in range(2,int(n**0.5)+2):
        if not n%i == 0:
            continue
        if check_primary(i):
            r=i
            count_r=1
            while(True):
                if n%r** (count_r+1) > 0:
                    break
                count_r+=1
            primaries.append([r,count_r])
        
        if check_primary(n//i):
            r=n//i
            count_r=1
            while(True):
                if n%r** (count_r+1) > 0:
                    break
                count_r+=1
            primaries.append([r,count_r])
        
    
    if len(primaries) ==0:
        primaries=[[n,1]]
    return primaries

N =int(input())

N_primaries=find_primary(N)
N1_primaries=find_primary(N-1)
ans=int(np.prod([e_tmp+1 for r_tmp,e_tmp in N1_primaries]) )

for r,e in N_primaries:
    residuals=1
    for r_tmp, e_tmp in N_primaries:
        if r_tmp == r:
            continue
        residuals*=((r_tmp%r)**e_tmp)%r
        residuals%=r
    if residuals%r==1:
        ans+=1

print(ans)

Submission status: Wrong Answer

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

b = len(div)
print(b+1)

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
n = int(input())

import collections
c = dict(collections.Counter(prime_factorize(n)))
ans = []
for i in range(2, int(n**0.5)+2):
    if i in c:
        if (n//(i**c[i]))%i == 1:
            ans.append(i)
    else:
        if n%i == 1:
            ans.append(i)

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

ans.extend(make_divisors(n-1))
ans.append(n)
answer = list(set(ans))
print(len(answer)-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i+2) for i in range(n-1)]
for i, ai in enumerate(a):
    m = n
    while m % ai == 0:
        if m >= ai and m % ai ==0:
            m = m / ai
    if m % ai != 1:
        a[i] = 0
b = set(a)
print(len(b) - 1)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())

b = []
l = []

ans = 2

for i in range(1, math.ceil(n ** 0.5)):
    if n % i == 0:
        l.append([n//i, i])
    elif (n - 1) % i == 0:
        b.append([(n - 1) // i, i])

ans += len(b) * 2

for x, y in l[1:]:
    while True:
        if x % y == 0:
            x //= y
        else:
            if x % y == 1:
                ans += 1
            break
        


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
def countfact(n,rem):
    if n!=1:
        for i in range(2,int(math.sqrt(n))+2):
            if n%i==0:
                a,b=n//i,i
                #print(a,'fac1',b,'fac2')
                if a!=1:
                    rem.add(a)
                if b!=1:
                    rem.add(b)
n=int(sys.stdin.readline())
count=0
temp=n
rem=set()
rem.add(n-1)
vis=defaultdict(int)
countfact(n-1,rem)
for i in rem:
    vis[i]=1

vis[1]=1
for i in range(2,int(math.sqrt(n))+2):
    if n%i==0:
        a,b=n//i,i
        c=0
        if b>a and vis[a]==0:
            while a%1==0 and b>a:
                vis[a]=1
                #print(a,'before')
                if b%a==1:
                    c+=1
                a=math.sqrt(a)
                #print(a,'a')
        elif vis[b]==0:
            while b%1==0 and a>b:
                #print(b,'before')
                vis[b]=1
                if a%b==1:
                    c+=1
                b=math.sqrt(b)
                #vis[b]=1
                #print(b,'after')
        count+=c
        #countfact(b-1,rem)
#print(count,'count')       
ans=len(rem)+count
if 1 in rem:
    ans-=1
#print(rem,'rem')
#print(ans,'ans')
count,z=1,True
while z:
    a=math.sqrt(n)
    #print(a,'a')
    if a%1==0:
        count+=1
    else:
        z=False
    n=a
print(ans+count)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

ans = []
for n in range(1, int(N ** 0.5) + 1):
    if (N - 1) % n == 0:
        ans.append(n)
        ans.append((N - 1) // n)

print(len(set(ans)) + 1)

Submission status: Wrong Answer

Solution code:

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

    # divisors.sort()
    return divisors

def hantei(n):
    k = int(n**0.5)
    if k*(k+1) == n or (k-1)*k == n or (k+1)*(k+2) == n:
        return k
    else:
        return 0

res1 = make_divisors(N-1)
res2 = hantei(N)
if res2!=0:
    res1.append(res2)
res1.append(2)
res1.append(N)
res1.remove(1)


res3 = make_divisors(N)
res3.remove(1)
for val in res3:
    n = N
    while n >= val:
        if n % val == 0:
            n = n // val
        else:
            n = n%val
    if n == 1:
        res1.append(val)
        # print(K)
res = len(set(res1))
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

def check(x) :
  n = N
  while n >= N :
    if n % x == 0 :
      n //= x
    else :
      n %= x
      
  return n == 1
  
ret = 0
d = set([])
for x in divisors[1:] :
  if check(x) :
    ret += 1
    d.add(x)

N = N - 1

for i in range(1, N + 1) :
  if i * i > N : 
    break
    
  if N % i == 0 :
    if not i in d :
      ret += 1
    if i != N // i and not N // i in d :
      ret += 1
      
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def prime_factrize(n):
    b = defaultdict(int)
    while n % 2 == 0:
        b[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            b[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        b[n] += 1
    return b

n = int(input())
primes = prime_factrize(n)
if n not in primes.keys():
    primes[n] += 1
ans = 0
for k, v in primes.items():
    ans += (n // k ** v) % k == 1

primes1 = prime_factrize(n - 1)
x = 1
for i in primes1.values():
    x *= i + 1
ans += x - 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
def make_divisors(n):
  for i in range(2, int(n**0.5)+1):
    if n % i == 0:
      x = n//i
      while x%i == 0:
        x = x//i
      if x%i == 1:
        ans += 1
  return
def count_divisors(n):
  c = 0
  for i in range(1, int(n**0.5)):
    if n % i == 0:
      c += 2
  if n%int(n**0.5) == 0:
    if n==n//int(n**0.5):
      c += 1
    else:
      c += 2
  return c
ans = 0
def count_divisors(n):
  c = 0
  for i in range(1, int(n**0.5)):
    if n % i == 0:
      c += 2
  if n%int(n**0.5) == 0:
    if n==n//int(n**0.5):
      c += 1
    else:
      c += 2
  return c
ans += count_divisors(n-1)
def make_divisors(n):
  c = 0
  for i in range(2, int(n**0.5)+1):
    if n % i == 0:
      x = n//i
      while x%i == 0:
        x = x//i
      if x%i == 1:
        c += 1
  return c
ans += make_divisors(n)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
K = int(stdin.readline().rstrip())


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


fact = factorize(K-1)
ans = 1

if len(fact) == 1:
    for i, j in (factorize(K-2)):
        ans *= (j+1)
    print(ans)

else:
    for i, j in (factorize(K-1)):
        ans *= (j+1)
    print(ans+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    if n == 2:
        print(1)
        return
    if n == 3:
        print(2)
        return
    ans = 0
    for i in range(2, int(sqrt(n)) + 1):
        m = n
        if m % i == 0:
            while m % i == 0:
                m //= i
            if m % i == 1:
                ans += 1
    m = n - 1
    l = []
    for i in range(2, int(sqrt(m)) + 1):
        t = 0
        while m % i == 0:
            m //= i
            t += 1
        if t:
            l.append(t)
    if m:
        l.append(1)
    tmp = 1
    for li in l:
        tmp *= (li + 1)
    print(ans+tmp)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
## F
import numpy as np

def check_primary(n):
    Is_Primary=True
    for j in range(2,int(n**0.5)+2):
        if n%j==0:
            Is_Primary=False
            break
    if n==2:
        Is_Primary=True
    return Is_Primary

def find_primary(n):
    primaries=[]
    for i in range(2,int(n**0.5)+2):
        if not n%i == 0:
            continue
        if check_primary(i):
            r=i
            count_r=1
            while(True):
                if n%r** (count_r+1) > 0:
                    break
                count_r+=1
            primaries.append([r,count_r])
        
        if check_primary(n//i):
            r=n//i
            count_r=1
            while(True):
                if n%r** (count_r+1) > 0:
                    break
                count_r+=1
            primaries.append([r,count_r])
        
    
    if len(primaries) ==0:
        primaries=[[n,1]]
    return primaries

N =int(input())

N_primaries=find_primary(N)
N1_primaries=find_primary(N-1)
ans=int(np.prod([e_tmp+1 for r_tmp,e_tmp in N1_primaries]) )

for r,e in N_primaries:
    residuals=1
    for r_tmp, e_tmp in N_primaries:
        if r_tmp == r:
            continue
        residuals*=((r_tmp%r)**e_tmp)%r
    if residuals%r==1:
        ans+=1

print(ans)

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):
    if x % i == 0:
        d = x // i
        if d % i == 0 or d % i == 1:
            divisor.add(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:
import sys
input = sys.stdin.readline

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 = set()

a = prime_factorize(n)

from collections import Counter

c = Counter(a)

for i in c.keys():
    tmp = 1
    for j in c.keys():
        if j != i:
            tmp *= pow(j, c[j])
    if (tmp - 1) % i == 0:
        ans.add(i)

#約数の列挙
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

d = make_divisors(n - 1)

for i in d:
    if i != 1:
        ans.add(i)

ans.add(n)

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