Problem:


Score : 600 points

Problem Statement

Given is a positive integer N.

We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.

Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.

In how many choices of K will N become 1 in the end?

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of choices of K in which N becomes 1 in the end.

Sample Input 1

6

Sample Output 1

3

There are three choices of K in which N becomes 1 in the end: 2, 5, and 6.

In each of these choices, N will change as follows:

When K=2: 6 \to 3 \to 1

When K=5: 6 \to 1

When K=6: 6 \to 1

Sample Input 2

3141

Sample Output 2

13

Sample Input 3

314159265358

Sample Output 3

9



Sample input:
6


Sample output:
3

Submission status: Wrong Answer

Solution code:
from 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)
            print(tmp)

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

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

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))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
li=[]
for i in range(2,math.floor(n**0.5)+1):
    if n%i==0:
        li.append(i)
        li.append(n//i)
li.append(n)
for i in li:
    x = n
    while x % i == 0:
        x //= i
    if x % i == 1:
        cnt += 1
print(ans - 1 + cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5)
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

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

ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5)
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

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

ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Wrong Answer

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

n=int(input())
divs1=divisors(n)
divs2=divisors(n-1)
cnt=len(divs2)-1
for val in divs1:
  if val==1:
    continue
  tmp=n
  while tmp%val==0:
    tmp=tmp//val
  if tmp%val==1:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5)
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

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

ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Wrong Answer

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

n=int(input())
divs1=divisors(n)
divs2=divisors(n-1)
cnt=len(divs2)
for val in divs1:
  if val==1:
    continue
  tmp=n
  while tmp%val==0:
    tmp=tmp//val
  if tmp%val==1:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
c=0
for i in range(2,int(n**0.5)+1):
    d=n
    while d%i==0:
        d//=i
    if n%i==0 and (d-1)%i==0:
        c+=1
for i in range(2,int((n-1)**0.5)+1):
    if (n-1)%i==0:
        if n-1==i**2:
            c+=1
        else:
            c+=2
print(c+2)

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5)
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5)
P0 = [N]
P1 = [N-1]
for i in range(2, n+1):
  if (N-1)%i == 0:
    if i == (N-1)//i:
      P1 += [i]
    else:
      P1 += [i, (N-1)//i]
  if N%i == 0:
    if i == N//i:
      P0 += [i]
    else:
      P0 += [i, N//i]

ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N = int(input())

P = prime(N - 1)

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

ans = 1
for i in P.keys():
  ans *= P[i] + 1

ans -= 1

P = prime(N)
D = [1]
for i in P.keys():
  L = len(D)
  n = i
  for j in range(P[i]):
    for k in range(L):
      D.append(D[k] * i)
    i *= i

for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= i * (t // i)
  if t == 1:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N = int(input())

P = prime(N - 1)

ans = 1
for i in P.keys():
  ans *= P[i] + 1

ans -= 1

P = prime(N)
D = [1]
for i in P.keys():
  L = len(D)
  n = i
  for j in range(P[i]):
    for k in range(L):
      D.append(D[k] * i)
    i *= i

for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= i * (t // i)
  if t == 1:
    ans += 1

print(ans)

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())
n_d = make_divisors(n)
n2_d = make_divisors(n-1)
#n-1の約数からnの約数を引く
ans_list = list(set(n2_d)-set(n_d))
#nも入れる
ans_list.append(n)
#nの約数から1とnを抜かす
n_d = list(set(n_d)-set({1, n}))
#nの約数からルートn未満のものを取り出す
n_d = [i for i in n_d if i<n**0.5]
#print(n_d)
for i in n_d:
    n_temp = n
    while(n_temp>=i):
        if n_temp%i==0:
            n_temp=n_temp//i
        else:
            n_temp-=i
    if n_temp==1:
        ans_list.append(i) 
print(len(ans_list))

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt, floor

def divisors(n):
    res = set([n])
    for i in range(2, floor(sqrt(n)) + 1):
        if n % i == 0:
            res.add(i)
            res.add(n // i)
    return res

n = int(sys.stdin.readline().rstrip())

def main():
    res = divisors(n - 1)
    cnt = len(res)
    for i in divisors(n):
        if i in res: continue
        m = n
        while m % i == 0:
            m //= i
        if (m - 1) % i == 0:
            cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#(i)N%K!=0の時、N-Kを繰り返すことになるためN-K%K=N%Kより
#N%K=1にならないといけない
#よってこのようなKはN-1が最大であり、他は全てN-1の約数であり、(そのほかにない)
#(証)
#N-1%K=0より直ちに従う(ただし、K=1の時N%1=0なので注意)
#よって、N-1を素因数分解して、チャチャチャっとやって…終わり！

#(ii)N%K==0の時、約数をO(sqrt(N))で全探査し、
#高々2*(sqrt(N))の約数KについてO(log(N))オーダーで(N/K^i)%K=1かを調べる

import math
N=int(input())
l=[]
ser=[]
#(i)の部分
#素因数分解
pf={}
ans1=1
m=N-1
buf=0
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)	#これでlistになったろう
ans1=1
for i in range(len(keys)):
    ans1=ans1*(l[i][1]+1)
ans1=ans1-1
#print(ans1)

#(ii)の部分
ans2=0
for i in range(int(math.sqrt(N))):
    a=i+1
    b=N/a
    #print(a)
    if b.is_integer()==True:
        if a!=b:
            ser.append(a)
            ser.append(int(b))
        else:
            ser.append(a)
for i in range(len(ser)):
    buf=N
    if ser[i]!=1:
        while buf//ser[i]>0:
            buf=buf//ser[i]
            #print(buf,ser[i])
        if buf%ser[i]==1:
            ans2=ans2+1
#print(ser,ans2)
print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5)
P0 = [N]
P1 = [N-1]
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1 += [i, (N-1)//i]
  if N%i == 0:
    P0 += [i, N//i]

ans = len(P1)
for p in P0:
  ans += check(p)

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

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

Submission status: Wrong Answer

Solution code:
import math
import collections

N = int(input())
res = 1


n = 10 ** 6 + 5000
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


def yakusuu(N):
    t = math.floor(math.sqrt(N))
    res = []
    for i in range(2, t + 1):
        if N % i == 0:
            res.append(t)
    return res


tres = prime_factorize(N - 1)
ctres = collections.Counter(tres)
for s in ctres.values():
    res *= s + 1
tres = yakusuu(N)
if len(tres) != 0:
    for c in tres:
        t = N
        while t % c == 0:
            t //= c
        if t == 1 or (t - 1) % c == 0:
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
n = int(input())
if n == 2:
    print(1)
    exit()
# n-1の約数を全列挙か、n の約数を全部探索して、n//k*p = 1+k*qになるかを確かめる
def divisor(n):
    res = [n]
    for i in range(2,1+math.ceil(math.sqrt(n))):
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i)
    return res
ans = len(divisor(n-1))
# n の約数で全列挙
res = []
lis = divisor(n)
for i in lis:
    # n を i で割れるだけわる
    m = n
    while m % i == 0:
        m = m // i 
    if m % i == 1:
        ans += 1
        res.append(i)
        #print(m,i)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
n = int(input())
if n == 2:
    print(1)
    exit()
# n-1の約数を全列挙か、n の約数を全部探索して、n//k*p = 1+k*qになるかを確かめる
def divisor(n):
    res = [n]
    for i in range(2,math.ceil(math.sqrt(n))):
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i)
    return res
ans = len(divisor(n-1))
# n の約数で全列挙
res = []
lis = divisor(n)
for i in lis:
    # n を i で割れるだけわる
    m = n
    while m % i == 0:
        m = m // i 
    if m % i == 1:
        ans += 1
        res.append(i)
        #print(m,i)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

k = 2
count = 1
while k * k <= n:
    m = n
    while m % k == 0:
        m = m / k
    if m % k == 1:
        count += 1
    k += 1

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

if n == 2:
    print(1)
else:
    print(count)

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):
    if n%i==0:
        if i in B.keys():
            if (n // (i ** B[i])) % i == 1:
                cnt+=1
        if (i-1)%(n//i)==0:
            cnt+=1
print(ans-1+cnt)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
    for i in range(len(ans)):
        ans.append(N//ans[i])
    return ans

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

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(p):
  _N = N
  while True:
    if _N%p == 0:
      _N = _N//p
    else:
      return (_N-1)%p == 0

n = int(N**0.5)
P0 = [N]
P1 = [N-1]
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1 += [i, (N-1)//i]
  if N%i == 0:
    P0 += [i, N//i]

ans = len(P1)
for p in P0:
  ans += check(p)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
n_set = set()
_n_ls = set()
for i in range(1, 10**6):
    if n % i == 0:
        n_set.add(i)
        n_set.add(n // i)
    if (n-1) % i == 0:
        _n_ls.add(i)
        _n_ls.add((n-1) // i)

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

cnt = len(_n_ls)
if 1 in _n_ls:
    cnt -= 1
for i in list(n_set):
    if i == 1:
        continue
    if check(n, i):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
N_tmp = N

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

cnt = 0
divisors = make_divisors(N)
divisors.append(N-1)
for K in divisors:
    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 math
n = int(input())
n=n-1
cnt=0
for i in range(2,int(math.sqrt(n))+1):
    if n%i==0:
        cnt=cnt+2
if int(math.sqrt(n)) == math.sqrt(n):
    cnt=cnt-1
if n%2==1:
    cnt=cnt+1
if n==1:
    print(1)
else:
    print(cnt+2)

Submission status: Wrong Answer

Solution code:
N = int(input())

res = 2

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

for i in range(2, int(N**0.5 + 0.5) + 1):
    if N % i != 0:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if (tmp - 1) % i == 0 and tmp >= i:
        res += 1
    if i ** 2 == N:
        continue
    tmp = N
    while tmp % (N // i) == 0:
        tmp //= (N // i)
    if (tmp - 1) % (N // i) == 0 and tmp >= N // i:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())

res = 2

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

for i in range(2, int(N**0.5 + 0.5) + 1):
    if N % i != 0:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if (tmp - 1) % i == 0 and tmp >= i:
        res += 1
    if i ** 2 == N:
        continue
    tmp = N
    while tmp % (N // i) == 0:
        tmp //= (N // i)
    if (tmp - 1) % (N // i) == 0 and tmp >= N // i:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
res = 1


n = 10 ** 6 + 5000
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)
if len(ctres) != 1:
    for c in ctres.keys():
        t = N
        while t % c == 0:
            t //= c
        if t == 1 or (t - 1) % c == 0:
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
n = int(input())
# n-1の約数を全列挙か、n の約数を全部探索して、n//k*p = 1+k*qになるかを確かめる
def divisor(n):
    res = [n]
    for i in range(2,math.ceil(math.sqrt(n))):
        if n % i == 0:
            res.append(i)
            res.append(n//i)
    return set(res)
ans = len(divisor(n-1))
# n の約数で全列挙
res = []
lis = divisor(n)
for i in lis:
    # n を i で割れるだけわる
    while n % i == 0:
        n = n // i 
    if (n-1) % i == 0:
        ans += 1
        res.append(i)
print(ans)
#print(divisor(n-1),res)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
    for i in range(len(ans)):
        ans.append(N//ans[i])
    return ans

N = int(input())
ans = 0
fn = factor(N)
fn2 = factor(N-1)
for i in range(1,len(fn2)):
    if N%fn2[i] == 1:
        ans += 1

for j in range(1,len(fn)):
    tmp = N
    while 1:
        if tmp%fn[j] == 0:
            tmp //= fn[j]
        else:
            if tmp%fn[j] == 1:
                ans += 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

res = 2

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

for i in range(2, int(N**0.5 + 0.5) + 1):
    if N % i != 0:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if (tmp - 1) % i == 0 and tmp >= i:
        res += 1
    if i ** 2 == N:
        continue
    tmp = N
    while tmp % (N // i) == 0:
        tmp //= (N // i)
    if (tmp - 1) % (N // i) == 0 and tmp >= N // i:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
num = 0

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

    # divisors.sort()
    return divisors


def warizan(x,k):
    a = 1
    for _ in range(1000000000):
        if x % (k**(a+1)) != 0:
            break
        else:
            a += 1
    return int(x/(k**a))
  
ans_list=[]
k_list = make_divisors(N)
for k in k_list:
    x = warizan(N,k)
    if (x-1) % k == 0:
        ans_list.append(x)

k_list_2 =  make_divisors(N-1)
ans_list.extend(k_list_2)
print(len(set(ans_list)))

Submission status: Wrong Answer

Solution code:
import math
 
N = int(input())
 
cnt = 0
 
if N == 2:
  print(2)
  exit()
 
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
res1 = sorted(make_divisors(N))
res1 = res1[1:math.ceil(len(res1)/2)]
 
for num in res1:
  kensa = N
  while True:
    if kensa % num == 0:
      kensa = kensa // num
      continue
    break
  if kensa % num == 1:
    cnt += 1
 
res2 = sorted(make_divisors(N-1))
cnt += len(res2[1:])+1
 
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

k = 2
count = 1
while k * k <= n:
    m = n
    while m % k == 0:
        m = m / k
    if m % k == 1:
        count += 1
    k += 1

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

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
num = 0

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

    # divisors.sort()
    return divisors


def warizan(x,k):
    a = 1
    for _ in range(1000000000):
        if x % (k**(a+1)) != 0:
            break
        else:
            a += 1
    return x/(k**a)
  
ans_list=[]
k_list = make_divisors(N)
for k in k_list:
    x = warizan(N,k)
    if (x-1) % k == 0:
        ans_list.append(x)

k_list_2 =  make_divisors(N-1)
ans_list.extend(k_list_2)
print(len(set(ans_list)))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

cnt = 0

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

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
res1 = sorted(make_divisors(N))
print(res1)
res1 = res1[1:math.ceil(len(res1)/2)]

for num in res1:
  kensa = N
  while True:
    if kensa % num == 0:
      kensa = kensa // num
      continue
    break
  if kensa % num == 1:
    cnt += 1

res2 = sorted(make_divisors(N-1))
cnt += len(res2[1:])+1

print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

cnt = 0

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

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
res1 = sorted(make_divisors(N))
res1 = res1[1:math.ceil(len(res1)/2)]

for num in res1:
  kensa = N
  while True:
    if kensa % num == 0:
      kensa = kensa // num
      continue
    break
  if kensa % num == 1:
    cnt += 1

res2 = sorted(make_divisors(N-1))
cnt += len(res2[1:])+1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())

res = 2

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

for i in range(2, int(N**0.5 + 0.5) + 1):
    if N % i != 0:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if (tmp - 1) % i == 0 and tmp >= i:
        res += 1
    if i ** 2 == N:
        continue
    tmp = N
    while tmp % (N // i) == 0:
        tmp //= (N // i)
    if (tmp - 1) % (N // i) == 0 and tmp >= N // i:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
import math


def judge(n, k):
    m = n % k
    while m == 0:
        n //= k
        m = n % k
    return m


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

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

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

        if judge(N, i) == 1:
            cnt += 1

    print(cnt)


main()

Submission status: Wrong Answer

Solution code:
N=int(input())
data=[]
for i in range(1,10**6+1):
    if (N-1)%i==0:
        j=(N-1)//i
        k=i
        if j!=1:
            data.append(j)
        if k!=1:
            data.append(k)

if not data:
    data.append(N-1)
    
data=set(data)
data=list(data)
data=sorted(data)
ans=len(data)



Data=[]

for i in range(1,10**6+1):
    if N%i==0:
        j=N//i
        k=i
        if j!=k:
            Data.append(j)
            Data.append(k)
            
        elif j==k:
            Data.append(j)
if not Data:
    Data.append(N)


Data=sorted(Data)
Data=list(set(Data))

from fractions import gcd
for num in Data:
    ori=N
    if num>1:
        while ori>=num :
            if ori%num==0:
                ori=ori//num
            else:
                ori=ori%num
        if ori==1:
            ans+=1
      

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

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

Submission status: Wrong Answer

Solution code:
import math


def judge(n, k):
    m = n % k
    while m == 0:
        n //= k
        m = n % k
    return m


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

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

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

        if judge(N, i) == 1:
            cnt += 1

    print(cnt)


main()

Submission status: Wrong Answer

Solution code:
import math


def judge(n, k):
    m = n % k
    while m == 0:
        n //= k
        m = n % k
    return m


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

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

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

        if judge(N, i) == 1:
            cnt += 1

    print(cnt)


main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())

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

res = 2

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

for i in range(2, int(N**0.5 + 0.5) + 1):
    if N % i != 0:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if (tmp - 1) % i == 0:
        res += 1
    if i ** 2 == N:
        continue
    tmp = N
    while tmp % (N // i) == 0:
        tmp //= (N // i)
    if (tmp - 1) % (N // i) == 0:
        res += 1

print(res)

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[1:]:
        n = N
        while n % i == 0:
            n = n // i
        if n % i == 1:
            count += 1

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

Submission status: Wrong Answer

Solution code:
import math


def judge(n, k):
    m = n % k
    while m == 0:
        n //= k
        m = n % k
    return m


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

    N1 = N - 1
    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

        if judge(N, i) == 1:
            cnt += 1

    print(cnt)


main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

n = ni()
p = divisor(n)
q = divisor(n-1)
ans = 0
for x in p + q:
  m = n
  if x == 1: continue
  while m % x == 0:
    m //= x
  if m % x == 1:
    ans += 1
print(ans)