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:
import sys
sys.setrecursionlimit(10 ** 5)

from math import factorial as fact
n = int(input())
if n == 1:
  print(1)
  exit()

def f(n, k):
  if n < k:
    return n
  if n % k == 0:
    return f(n/k, k)
  else:
    return n % k
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[tmp] = p.get(tmp, 0) + 1
ans = 1
for pp in p.values():
  ans *= pp + 1
ans -= 1
tmp = n

p = {}
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

for pp in p:
  if f(n, pp) == 1:
    ans += 1
      

print(ans + 1)

Submission status: Wrong Answer

Solution code:
N=int(input())

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

for i in range(2, int(N**0.5//1)+1):
    temp=N
    if temp%i==0:
        while temp%i==0:
            temp//=i
        if  temp%i==1:
          ans+=1
          
        temp=N  
        i=N//i
        while temp%i==0:
            temp//=i
        if  temp%i==1:
          ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import math


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


def main():
    N = int(input())
    ans = 2  #K=N-1,N

    # N%K != 0
    M = N-1
    k = 2
    while k**2 < M:
        if M%k==0:
            ans += 2
        k += 1
    rt = int(math.sqrt(M))
    ans += (rt**2 == M)

    # N%K==0
    k = 2
    while k**2 <= N:
        ans += (N%k==0 and simulate(N, k))
        k+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
count = set([n,n-1])

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

print(len(count))

Submission status: Wrong Answer

Solution code:
import math


def main():
    N = int(input())
    cnt = 0

    N1 = N - 1
    cnt = 2
    for i in range(2, int(math.sqrt(N1)) + 1):
        if N1 % i == 0:
            cnt += 2

    for i in range(2, int(math.sqrt(N)) + 1):
        if N % i != 0:
            continue

        m = N // i
        n = m
        while n % i == 0:
            n //= i
        if n % i == 1:
            cnt += 1

        n = N // m
        i = m
        while n % i == 0:
            n //= i
        if n % i == 1:
            cnt += 1

    print(cnt)


main()

Submission status: Wrong Answer

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

from math import factorial as fact
n = int(input())
if n == 1:
  print(1)
  exit()

def f(n, k):
  if n < k:
    return n
  if n % k == 0:
    return f(n/k, k)
  else:
    return n % k
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[tmp] = p.get(tmp, 0) + 1
ans = 1
for pp in p.values():
  ans *= pp + 1

tmp = n

p = {}
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

for pp in p:
  if f(n, pp) == 1:
    ans += 1
      

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def PF(n):
    res = {}
    m = int(n**0.5)
    for i in range(2,m+1):
        cnt = 0
        while n % i == 0:
            n = n//i
            cnt+=1
        if cnt > 0:
            res[i] = cnt
    if n > 1:
        res[n] = 1
    return res

ans = 0
# N|K
pf = PF(N)
ps,fs = zip(*pf.items())
cand = []
pss = []
for p,f in pf.items():
    pss.extend([p]*f)
pts = set([1])
for p in pss:
    nps = [q*p for q in pts]
    pts = pts.union(nps)
for p in pts:
    if p == 1:
        continue
    M = N
    while M % p == 0:
        M //= p
    if M % p == 1:
        cand.append(p)

# N |/ K
M = int(N**0.5+1)
cand2 = [i for i in range(2,M) if N % i == 1]
for m in cand2[:]:
    k = (N-1)//m
    cand2.append(k)
cand.append(N-1)

cand2 = set(cand2)
print(len(cand)+len(cand2))

Submission status: Wrong Answer

Solution code:
import math


def main():
    N = int(input())
    cnt = 0

    N1 = N - 1
    cnt = 1
    for i in range(2, int(math.sqrt(N1)) + 1):
        if N1 % i == 0:
            cnt += 2

    cnt += 1
    for i in range(2, int(math.sqrt(N)) + 1):
        if N % i != 0:
            continue

        n = N // i
        while n % i == 0:
            n //= i
        if n % i == 1:
            cnt += 1

    print(cnt)


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)
b=factorization(n-1)
la=len(a)
lb=len(b)
sum=1
for i in range(lb):
  sum*=b[i][1]+1

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

l=[]
for j in range(la):
  l.append(a[j][1])
c=gcdlist(l)

if c>1:
  d=factorization(c)
  count=1
  for j in range(len(d)):
    count*=d[j][1]+1
  sum+=count
else:
  count=0
  for k in range(la):
    x=a[k][0]
    y=x**a[k][1]
    if (n/y-1)%x==0:
      count+=1
  sum+=count
print(sum)

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:
        c += 2

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:
from itertools import product

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 _num(arr):
    out = 1
    for item in arr:
        out *= (item[1]+1)
    return out

n_orig = int(input())
arr = factorization(n_orig)
arr1 = factorization(n_orig - 1)

if len(arr)==1 and arr[0][1]==1:
    print(_num(arr1))
else:
    tmp = _num(arr1)-1
    
    for nums in product(*[range(item[1]+1) for item in arr]):
        n = n_orig
        kk = 1
        for num, base in zip(nums, arr):
            base = base[0]
            kk *= base**num
        if (kk==1):
            continue
        while n%kk==0:
            n /= kk
        if ((n - 1) % kk == 0):
            tmp += 1
    print(tmp)

Submission status: Wrong Answer

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

import collections
A=collections.Counter(prime_factorize(n-1))
B=collections.Counter(prime_factorize(n))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
for i in range(1,math.floor(n**0.5)+1):
    x=n
    if n%i==0:
        if n//(i**B[i])%i==0:
            cnt+=1
        if (i-1)%(n//i)==0:
            cnt+=1

print(ans-2+cnt)

Submission status: Wrong Answer

Solution code:
from itertools import product

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 _num(arr):
    out = 1
    for item in arr:
        out *= (item[1]+1)
    return out

n_orig = int(input())
arr = factorization(n_orig)
arr1 = factorization(n_orig - 1)

if len(arr)==1 and arr[0][1]==1:
    print(_num(arr1))
else:
    tmp = _num(arr1)-1
    
    for nums in product(*[range(item[1]+1) for item in arr]):
        n = n_orig
        kk = 1
        for num, base in zip(nums, arr):
            base = base[0]
            kk *= base**num
        if (kk==1):
            continue
        while n%kk==0:
            n /= kk
        if ((n - 1) % kk == 0):
            print(kk)
            tmp += 1
    print(tmp)

Submission status: Wrong Answer

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math

#input
#N
#A1 A2 ... AN
N = int(input())


def yakusuu(n):
    #約数全列挙
    l = []
    border = int(math.sqrt(n))
    #print(border) #ここまでしか考えなくて良い
    for i in range(1, border+1):
        #print(i)
        if(n % i == 0):
            l.append(i)
            l.append(int(n/i))
    return l

#print(yakusuu(N))
#print(yakusuu(N-1))
N_yaku = yakusuu(N)
N_1_yaku = yakusuu(N-1)
if(len(N_yaku) != 1):
    del N_yaku[0]
if(len(N_yaku) >= 2 and N_yaku[-1] == N_yaku[-2]):
    del N_yaku[-1]
if(len(N_1_yaku) != 1):
    del N_1_yaku[0]
if(len(N_1_yaku) >= 2 and N_1_yaku[-1] == N_1_yaku[-2]):
    del N_1_yaku[-1]
#print('N_yaku:{}'.format(N_yaku))
#print('N_1_yaku:{}'.format(N_1_yaku))
counter = 0
#N-1の約数であるとき→Nの約数でなければOK
#NとN-1は互いに素なので気にしなくてよかった
'''
for i in N_1_yaku:
    #print(i)
    #print(i in N_yaku)
    if( (i in N_yaku) == False ) :
        print('false_hit:i:{}'.format(i))
        counter += 1
'''
counter += len(N_1_yaku)



#Nの約数であるとき
def hantei_Nyaku(k):
    rep_N = N
    #count = 0
    while True:
        if(rep_N % k == 0):
            rep_N = int(rep_N / k)
            #print(rep_N)
        else:
            break
    if((rep_N - 1) % k == 0):
        return 'Yes'
    else:
        return 'No'



for i in N_yaku:
    #print('i:{}'.format(i))
    #print(hantei_Nyaku(i))
    if(hantei_Nyaku(i) == 'Yes'):
        #print('true_hit')
        counter+=1

print(counter)

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 divisor, degree in c.items():
    if (n//(divisor**degree))%divisor == 1:
        ans.append(divisor)

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))
answer = list(set(ans))
answer.sort()
answer.remove(1)
answer.append(n)
if n == 2:
    print(len(answer)-1)
else:
    print(len(answer))

Submission status: Wrong Answer

Solution code:
def rest(n, i):
    while n%i == 0:
        n //= i
    return n

N = int(input())
ans = [N-1, N]

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

print(len(set(ans)))

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 divisor, degree in c.items():
    if (n//(divisor**degree))%divisor == 1:
        ans.append(divisor)

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))
answer = list(set(ans))
answer.sort()
answer.pop(0)
answer.append(n)
if n == 2:
    print(len(answer)-1)
else:
    print(len(answer))

Submission status: Wrong Answer

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

for i in range(2,int(N**0.5)+2):
    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:
        c += 2

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
                break
    print(c+2)

Submission status: Wrong Answer

Solution code:
n = int(input())

fact = [n]
fact1 = [n-1]
i = 2
while i * i <= n:
    if n % i == 0:
        fact += [i]
        if n // i != i:
            fact += [n//i]
    i += 1

i = 2
while i * i <= n-1:
    if (n-1) % i == 0:
        fact1 += [i]
        if (n-1) // i != i:
            fact1 += [(n-1)//i]
    i += 1

ans = 0
for x in fact:
    k = n
    while k % x == 0:
        k //= x
    if k % x == 1:
        ans += 1

print(ans + len(fact1))

Submission status: Wrong Answer

Solution code:
def rest(n, i):
    while n%i == 0:
        n //= i
    return n

N = int(input())
ans = [N-1, N]

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

print(len(set(ans)))

Submission status: Wrong Answer

Solution code:
MAX_PRIME = 10**5
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor

n = int(input())
ans = 1
for _, c in factorization(n-1).items():
    ans *= c + 1

f = factorization(n)
k = list(f.keys())
def dfs(num, i):
    ret = 0
    if i == len(k):
        if num != 1:
            x = n
            while x % num == 0:
                x //= num
            if x % num == 1:
                ret += 1
        return ret
    else:
        p = k[i]
        for j in range(f[p]+1):
            ret += dfs(num * p ** j, i+1)
        return ret

print(dfs(1, 0) + ans - 1)

Submission status: Wrong Answer

Solution code:

n = 0

def format_input(filename = None):
	global n
	if filename == None:
		n = int(input())

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 10**12)
		print(n)

def judge(n, k):
	if n % k == 0:
		return judge(n // k, k)
	else:
		return (n % k == 1)

def get_answer():
	answer = 2
	for i in range(2, int(n ** 0.5) + 1):
		if (n - 1) % i == 0:
			answer += 2
			if n - 1 == i ** 2:
				answer -= 1
		elif judge(n, i):
			answer += 1
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
N_tmp = N
pf={}
for i in range(2,int(N**0.5)+1):
    while N%i==0:
        pf[i]=pf.get(i,0)+1
        N//=i
if N>1:pf[N]=1

kouho = [1]
for k in pf.keys():
    new_kouho = []
    for v in range(0, pf[k] + 1):
        for val in kouho:
            new_kouho.append(val * k ** v)
        kouho.extend(new_kouho)

cnt = 0
new_kouho = []
for v in sorted(list(set(kouho)))[1:]:
    for base in range(-1, 1):
        new_kouho.append(v + base)

for K in sorted(list(set(new_kouho))):
    tmp_N = N_tmp
    if K <= 1: continue
    if tmp_N % K == 0:
        tmp_N = (tmp_N // K) % K
    else:
        tmp_N = tmp_N % K
    if tmp_N == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
count = set([2,n,n-1])

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

print(len(count))

Submission status: Wrong Answer

Solution code:
def divisors(n):
    x = []
    m = 1
    while m * m <= n:
        if n % m == 0:
            x.append(m)
            x.append(n // m)
        m += 1
    return x

n = int(input())
d = divisors(n)
ans = 0
for k in d:
    if k == 1:
        continue
    nn = n
    while nn % k == 0:
        nn = nn // k
    ans += nn % k == 1

d1 = divisors(n - 1)
ans += len(d1) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
def factorization(x):
  ret=[]
  tf=0
  while tf!=1:
    for i in range(2,math.floor(x**0.5)+1):
      if x%i==0:
        x=x//i
        ret+=[i]
        break
      if i==math.floor(x**0.5):
        tf=1
  ret+=[x]
  return(ret)
N_fac=factorization(N)
dic1={}
for i in N_fac:
  if i not in dic1:
    dic1[i]=1
  else:
    dic1[i]=dic1[i]+1
ans=0
plis=[]
tf2=0
for i in dic1.values():
  p=i
  if len(plis)!=1:
    plis+=[p]
  if p!=plis[0]:
    tf2=1
    break
if tf2==0:
  ans+=1
N1_fac=factorization(N-1)
dic2={}
for i in N1_fac:
  if i not in dic2:
    dic2[i]=1
  else:
    dic2[i]=dic2[i]+1
d=1
for i in dic2.values():
  d=d*(i+1)
ans=ans+d
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N == 2:
	print(1)
	exit()
if N == 3:
	print(2)
	exit()
def yakusu(n):
	rn = int(n ** 0.5)
	ret = 2
	for i in range(2, rn):
		if n % i == 0:
			ret += 2
	if rn*rn == n:
		ret += 1
	return ret

#A = [True for i in range(10**6 + 1)]
ans = 1 # K = N
rn = int(N ** 0.5)
for i in range(2, rn+1):
	if N % i > 0:
		continue
	n = N
	while n % i == 0:
		n = n // i
	if n % i == 1:
		ans += 1
	n = N
	j = N // i
	if j <= i:
		continue
	while n % j == 0:
		n = n // j
	if n % j == 1:
		ans += 1
print(ans + yakusu(N-1) - 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)
    return divisors

divlist = make_divisors(N)
count = 0
if len(divlist) != 2:
    for i in divlist[2:]:
        temp = N // i
        if temp % i == 1:
            count += 1

print(count + len(make_divisors(N-1)))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
import math


def divisor(n):
    divs = list()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divs.append(i)
            if i * i != n:
                divs.append(n // i)
        i += 1
    return list(sorted(divs))


def read():
    N = int(input())
    return N,


def solve(N):
    ptn = deque()
    factors = divisor(N-1)
    return len(factors) + 1
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())

res = 1

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def factorization(n):
    if n == 1: return [1]
    res = []
    x = n
    y = 2
    while y * y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1: res.append(x)
    return res

F = factorization(N - 1)

C = Counter(F)

for v in C.values():
    res *= v + 1

res -= 1

F = factorization(N)
C = Counter(F)
A = list(C.items())
L = len(A)

for i in range(2**L):
    if i == 0:
        continue
    tmp = 1
    tmp2 = 0
    tmp3 = 1
    for j in range(L):
        if (i >> j) & 1:
            tmp *= A[j][0] ** A[j][1]
            tmp2 = gcd(tmp2, A[j][1])
            tmp3 *= A[j][0]
    tmp = N // tmp - 1
    for k in range(1, tmp2 + 1):
        if tmp2 % k != 0:
            continue
        if tmp >= tmp3 ** k and tmp % (tmp3 ** k) == 0:
            res += 1

print(res + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
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
n = int(input())
if n == 2:
    print(0)
elif n == 3:
    print(2)
elif n == 4:
    print(3)
else:
    count = 2
    check_list = make_divisors(n-1)
    count += len(check_list)
    check_list = make_divisors(n)
    for k in check_list:
        temp_n = n // k
        while(True):
            if temp_n % k == 0:
                temp_n = temp_n // k
            elif temp_n % k == 1:
                count += 1
                break
            else:
                break
    print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
N_tmp = N
pf={}
for i in range(2,int(N**0.5)+1):
    while N%i==0:
        pf[i]=pf.get(i,0)+1
        N//=i
if N>1:pf[N]=1

kouho = [1]
for k in pf.keys():
    new_kouho = []
    for v in range(0, pf[k] + 1):
        for val in kouho:
            new_kouho.append(val * k ** v)
            new_kouho.append(val * k ** v - 1)
        kouho.extend(new_kouho)

cnt = 0
for v in sorted(list(set(kouho)))[1:]:
    K = v
    tmp_N = N_tmp
    if K <= 1: continue
    if tmp_N % K == 0:
        tmp_N = (tmp_N // K) % K
    else:
        tmp_N = tmp_N % K
    if tmp_N == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import collections
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())
count = 1

n = collections.Counter(prime_factorize(N - 1))
c = list(n.values())
for i in c:
    count = count * (i+1)
    
print(count+1)

Submission status: Wrong Answer

Solution code:


N = int(input())
ans = 0
num = 2
while num * num <= N:
    tmp = N
    while tmp % num == 0:
        tmp //= num
    
    if tmp == 1:
        ans += 1

    else:
        if tmp % num == 1:
            ans += 2

    

    num += 1

num -= 1

if num*num == N:
    ans += 1

print(ans+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
count = set([2,n,n-1])

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

print(len(count))

Submission status: Wrong Answer

Solution code:
# n以下の全ての素数のセットを返す関数
def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

def prime_factors(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

def rest(n, i):
    while n%i == 0:
        n //= i
    return n

N = int(input())
N_pf = set(prime_factors(N))
N_pf.add(N)
ans = [N-1]

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

ans2 = []
for k in N_pf:
    if (rest(N,k) - 1) % k == 0:
        ans.append(k)


print(len(set(ans)))

Submission status: Wrong Answer

Solution code:
N = int(input())

def yakusu(n):
	rn = int(n ** 0.5)
	ret = 0
	for i in range(1, int(n**0.5)):
		if n % i == 0:
			ret += 2
	if rn*rn == n:
		ret += 1
	return ret

#A = [True for i in range(10**6 + 1)]
ans = 1 # K = N
rn = int(N ** 0.5)
for i in range(2, rn+1):
	if N % i > 0:
		continue
	if i == 2:
		ans += 1
		continue
	n = N
	while n % i == 0:
		n = n // i
	if n % i == 1:
		ans += 1
	n = N
	j = N // i
	if j <= i:
		continue
	while n % j == 0:
		n = n // j
	if n % j == 1:
		ans += 1
print(ans + yakusu(N-1) - 1)

Submission status: Wrong Answer

Solution code:
K = int(input())
if K <= 3:
  print(K - 1)
else:
  cnt = 0
  right = int(K ** .5)
  for i in range(3, right):
    wkK = K
    while wkK % i == 0:
      wkK /= i
    if wkK % i == 1:
      cnt += 1
  print(cnt + 3)

Submission status: Wrong Answer

Solution code:
n = input()

m = n - 1
sqm = int(m ** 0.5) + 1

ans = set([m])
for i in xrange(2, sqm):
    if m % i == 0:
        ans.add(i)
        if i * i != m: ans.add(m // i)

divs = [n]
sqn = int(n ** 0.5) + 1
for i in xrange(2, sqn):
    if n % i == 0:
        divs.append(i)
        if i * i != n: divs.append(n // i)

for d in divs:
    N = n
    while N % d == 0: N //= d

    if N % d == 1: ans.add(d)

print len(ans)

Submission status: Wrong Answer

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

import collections
A=collections.Counter(prime_factorize(n-1))
B=collections.Counter(prime_factorize(n))

ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)
for a, b in B.items():
    if b>=2:
        for i in range(2,b+1):
            if (n//(a**i))%a==1:
                cnt+=1
import math
for i in range(1,math.floor(n**0.5)+1):
    if n%i==0:
        if ((n//i)-1)%i==0:
            cnt+=1
        if ((n//i)-1)%(n//i)==0:
            cnt+=1

print(ans-2+cnt)

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)

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

def yakusu(n):
	rn = int(n ** 0.5)
	ret = 0
	for i in range(1, int(n**0.5)):
		if n % i == 0:
			ret += 2
	if rn*rn == n:
		ret += 1
	return ret

#A = [True for i in range(10**6 + 1)]
ans = 1 # K = N
for i in range(2, min(N, 10**6+1)):
	if N % i > 0:
		continue
	if i == 2:
		ans += 1
		continue
	n = N
	while n % i == 0:
		n = n // i
	if n % i == 1:
		ans += 1
	n = N
	j = N // i
	while n % j == 0:
		n = n // j
	if n % j == 1:
		ans += 1
print(ans + yakusu(N-1) - 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())
nl = make_divisors(n)
nl_m = make_divisors(n-1)
l = sorted(list(set(nl + 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:
            p = 1
            break
        else:
            break
    if p == 1:
        ans += 1
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    n = int(input())
    ans = set([n])
    divisors = make_divisors(n)
    ans |= set(make_divisors(n-1))
    ans |= set(prime_factorize(n-1))
    ans |= set([divisor for divisor in divisors if ((n//divisor)%divisor)==1])
    ans -= set([1])
    print(len(ans))

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

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

if __name__ == "__main__":
    main()

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

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())
soin=factorization(n)
minus=factorization(n-1)
# print(soin)
# print(minus)
d={}

lst=make_divisors(n)
# print(lst)
for i in lst:
    d[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

for i in lst:
    if i!=1:
        tmp=make_divisors(i-1)
        for j in tmp:
            if j==1:
                continue
            if j in d:
                ans+=1

print(ans+1)

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