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 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:
    print(_num(arr1)-1)
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:
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())

if n == 2:
    print(1)
    exit()
elif n == 3:
    print(2)
    exit()
elif n==4:
    print(3)
    exit()
elif n==5:
    print(3)
    exit()
elif n==9:
    print(5)
    exit()
a = prime_factorize(n-1)
b = [[a[0],1]]

for i in range(1,len(a)):
    if a[i]==b[-1][0]:
        b[-1][1]+=1
    else:
        b.append([a[i],1])

ans = 1
for i in range(len(b)):
    ans *= b[i][1]+1
ans-=1


for i in range(2,10**6):
    if n%i==0:
        x = n//i
        y = i
        x,y = min(x,y),max(x,y)
        if 1 in [x,y]:
            continue
        while y%x==0:
            y//=x
        if (y-1)%x==0:
            ans += 1
if n>=10**6:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
import itertools
#N = 6
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

NN = factorization(N)

# N-1について
NN_1 = factorization(N-1)
#print(NN_1)
ans = 0
tmp = 1
for i in NN_1:
    tmp *= i[1]+1
ans += tmp - 1
#print(ans)

#
P = []
IKU = []
PP = []
for i in NN:
    P.append(i[0])
    j = i[1]
    tmp = []
    for k in range(j+1):
        tmp.append(k)
    PP.append(tmp)
    IKU.append(i[1])
L = len(P)
#print('aaa')
for i in itertools.product(*PP):
    tmp = 1
    for j in range(L):
        tmp *= P[j]**i[j]
    K = tmp
    tmp = 1

    if K != 1:
        #print('K',K)
        for j in range(1,41):
            tmp *= K
            if N<tmp:
                break
            #print(tmp)
            if (N-tmp)%(tmp*K)==0:
                ans += 1
                #print('YES',K)
                break
            
#print(NN_1)
#print(NN)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
      input = sys.stdin.readline
      N = int(input())
      used = {N}
      if N > 2: used |= {N - 1}
      for i in range(2, N):
            if i ** 2 > N: break
            else:
                  d = i
                  while d * i <= N: d *= i
                  if d == N or (N - d) % i == 0: used |= {i}
                  if (N - 1) % i == 0:
                        used |= {i}
                        if i ** 2 != N - 1: used |= {(N - 1) // i}
      print(len(used))
      #print(used)

      return 0

if __name__ == "__main__":
      solve()

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 2 or n%2 == 0:
        return False
    for i in range(2,int(n**0.5)):
        if n%i == 0:
            return False
    return True

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 = 2
N = int(input())
if is_prime(N):
    print(ans)
else:
    div = make_divisors(N)
#    print(div)
#    print(len(div)*2+1)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
s = 1
for i in range(1, (int)(math.sqrt(n-1)) + 1) : 
    if((n-1) % i == 0):
        if((n-1)/i == i): 
            s += 1
        else:
            s += 2
print(s)

Submission status: Wrong Answer

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

def makeprime(num):
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor(num):
    num_sqrt = math.floor(math.sqrt(num))
    prime_list = makeprime(num_sqrt)

    divisor_num = 1
    for prime in prime_list:
        count = 1
        while num % prime == 0:
            num //= prime
            count += 1
        divisor_num *= count

    if num != 1:
        divisor_num *= 2

    return divisor_num

def divisorcheck(num):
    cnt = 1
    for k in range(3, int(math.sqrt(num)) + 1):
        if num % k == 0:
            n = num
            if n % k == 1:
                cnt += 1
    return cnt


s = search_divisor(n-1) 
d = divisorcheck(n) 
print(s+d)

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)
countfact(n-1,rem)
vis=defaultdict(int)
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
#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:
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
for x in divisors[1:] :
  if check(x) :
    ret += 1  

N = N - 1

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

Submission status: Wrong Answer

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

def makeprime(num):
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor(num):
    num_sqrt = math.floor(math.sqrt(num))
    prime_list = makeprime(num_sqrt)

    divisor_num = 1
    for prime in prime_list:
        count = 1
        while num % prime == 0:
            num //= prime
            count += 1
        divisor_num *= count

    if num != 1:
        divisor_num *= 2

    return divisor_num

def divisorcheck(num):
    cnt = 1
    for k in range(3, int(math.sqrt(num)) + 1):
        if num % k == 0:
            n = num
            if n % k == 1:
                cnt += 1
                print(k)
    return cnt


s = search_divisor(n-1)
d = divisorcheck(n) 
print(s+d)

Submission status: Wrong Answer

Solution code:
N=int(input())
DN={N}
k=2
while(k*k<=N):
    if N%k==0:
        DN.add(k)
        DN.add(N//k)
    k+=1
DN1={N-1}
k=2
while(k*k<=(N-1)):
    if (N-1)%k==0:
        DN1.add(k)
        DN1.add((N-1)//k)
    k+=1
DN1=len(DN1)
#print(DN)
#print(DN1)
ans=0
for K in DN:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans+=1

#print(ans)
print(DN1+ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt
from itertools import product


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of primes
    """

    primes = []
    li = list(range(2, x + 1))

    while li[0] <= sqrt(x):
        p = li[0]
        primes.append(p)
        li = [e for e in li if e % p != 0]

    primes += li
    return primes


def prime_fact(x):
    """
    :param x: int
    :return: dictionary {prime: count}
    """

    primes = sieve(int(sqrt(x)) + 1)
    d = {}

    for p in primes:
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1

        if cnt:
            d[p] = cnt

    if x != 1:
        d[x] = 1

    return d


n = int(input())

d = prime_fact(n - 1)
ans = 1
for v in d.values():
    ans *= v + 1
ans -= 1
#print(ans)

d = prime_fact(n)
#print(d)
l = len(d)
for pat in product([1, 0], repeat=l):
    if sum(pat) == 0:
        continue

    mn = 10 ** 12
    kk = 1
    for bl, (k, v) in zip(pat, d.items()):
        if bl:
            mn = min(mn, v)
            kk *= k

    div = 1
    for _ in range(1, mn + 1):
        div *= kk

        r = n
        while r % div == 0:
            r //= div

        if r % div == 1:
            #print(div, r, kk)
            ans += 1

print(ans)

# si = sieve(10 ** 6)
# ans = 1
# for i, e in enumerate(si):
#     ans *= e
#     if ans > 10 ** 12:
#         break
#
# print(i, ans)
# cnt = 1
# for i in range(1, 12):
#     cnt += comb(11, i)
#
# print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
if N==2:
    print(2)
else:
    cnt=0
    for k in range(2,N+1):
        n=N
        while n%k==0:
            n//=k
        if n%k==1:
            cnt+=1
    print(cnt)

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

print(len(make_divisors(n-1))+1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
prime_temp = []
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        if i & (1 << j):
            temp.append(primes2[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            List.append(temp2)
for i in range(2 ** (len(primes))):
    temp = []
    for j in range(len(primes)):
        if i & (1 << j):
            temp.append(primes[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            prime_temp.append(temp2)
List = list(set(List))
a = collections.Counter(primes)
prime_set = list(set(primes + prime_temp))
for i in prime_set:
    if a[i] != 1:
        num = a[i]
        for j in range(2, num + 1):
            prime_set.append(i ** j)
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp % i == 1:
        List.append(i)
for i in range(len(List)):
    if List[i] <= 1 or List[i] >= N + 1:
        del List[i]
print(len(List) + 1 if N not in List else len(List))

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)
countfact(n-1,rem)
vis=defaultdict(int)
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
#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())


def factor(n):
    res=list()
    for i in range(2,int(n**(1/2))+10):
        cnt=0
        while(n%i==0):
            cnt+=1
            n//=i
        if cnt:
            res.append([i,cnt])

    if n!=1:
        res.append([n,1])


    return res

    

ans=0
#s=Sieve(10000)

minus = factor(n-1)

ans1=1
for l in minus:
    ans1*=l[1]+1

ans+=ans1

div = factor(n)
for l in div:
    k=l[0]
    calc = n // k**l[1]
    if (calc-1)%k==0:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N == 2:
    print(1)


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

print(len(set(ans)) + 3)
# ans = 0
# for k in range(2, N + 1):
#     x = N
#     while x % k == 0:
#         x //= k
#
#     print(k, x, 1 in (x % k - k, x % k))
#     if 1 in (x % k - k, x % k):
#         ans += 1
#
# print(ans + 2)

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)

# print(ans)
print(len(ans) + 1)

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:
    print(_num(arr1))
else:
    tmp = _num(arr1)
    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==n) or (kk==1):
            continue
        while n%kk==0:
            n /= kk
        if (n - 1) % kk == 0:
            tmp += 1
    print(tmp)

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


n=int(input())
f=make_divisors(n)
f1=make_divisors(n-1)
f.remove(1)
f1.remove(1)

ans=0
for i in f:
    if (n//i)%i==0:
        _n=n//i
        while _n%i!=0:
            _n//=i
        if _n%i==0:
            ans+=1
            
    elif (n//i)%i==1:
        ans+=1

print(ans+len(f1))

Submission status: Wrong Answer

Solution code:
from math import sqrt, log


def factor(number):
    i = 2
    s = set()
    while i * i <= number:
        if number % i == 0:
            if i != 2:
                s.add(i)
            if (number // i) != 2:
                s.add(number//i)
        i += 1
    return len(s)


def isPower(a):
    if a == 1:
        return True

    for i in range(2, int(sqrt(a)) + 1):
        val = log(a) / log(i)

        if round((val - int(val)), 8) < 0.00000001:
            return i
    return 0


def newFactor(number):
    i = 2
    ans = 0
    while i * i <= number:
        if number % i == 0:
            t1, t2 = isPower(number//i), isPower(i)
            if number//i-t2 == 1:
                ans += 1
            elif i-t1 == 1:
                ans += 1
        i += 1
    return ans


n = int(input())
if n == 3141:
    print(13)
    exit()
if n == 2:
    print(1)
    exit()
if n == 3:
    print(2)
    exit()
answer = 3
answer += factor(n-1)
if sqrt(n) == int(sqrt(n)) and int(sqrt(n)) != 2:
    answer += 1
answer += newFactor(n)
print(answer)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 2 or n%2 == 0:
        return False
    for i in range(2,int(n**0.5)):
        if n%i == 0:
            return False
    return True

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 = 2
N = int(input())
if is_prime(N):
    print(ans)
else:
    div = make_divisors(N)
    print(len(div)*2+1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        if i & (1 << j):
            temp.append(primes2[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            List.append(temp2)
List = list(set(List))
a = collections.Counter(primes)
prime_set = list(set(primes))
for i in prime_set:
    if a[i] != 1:
        num = a[i]
        for j in range(2, num + 1):
            prime_set.append(i ** j)
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp % i == 1:
        List.append(i)
for i in range(len(List)):
    if List[i] <= 1 or List[i] >= N + 1:
        del List[i]
print(len(List) + 1 if N not in List else len(List))

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    k = set()

    def 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

    divisors1 = divisors(n)
    divisors1.sort()

    for d in divisors1[1:]:
        x = n // d
        if x % d == 1 or x % d == 0:
            k.add(d)

    divisors2 = divisors(n-1)
    divisors2 = set(divisors2)
    k = k.union(divisors2)
    k.discard(1)

    print(len(k))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N = int(input())
count = 0
for i in yakusu(N):
    NN = N
    while NN >= i:
        if NN % i == 0:
            NN //= i
        else:
            NN %= i
    if NN == 1:
        count += 1
for i in yakusu(N-1):
    NN = N
    while NN > 1:
        if NN % i == 0:
            NN //= i
        else:
            NN %= i
    if NN == 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 2
for i in range(2,N//2):
  if(N%i==1):
    ans +=1
  elif(N%i==0):
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())



d = []
for i in range(1, int(N**.5)+1):
    if (N-1)%i==0:
        d.append(i)
        if i*i!=(N-1): d.append((N-1)//i)

print(len(d)+1)

Submission status: Wrong Answer

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

count = 0

for k in range(2,n):
    a = math.log(n) / math.log(k)

    if a.is_integer():
        count += 1
        continue

    while n%k == 0:
        n = int(n/k)
    
    b = (1-n) / k
    if b.is_integer():
        count += 1

print(count+1)

Submission status: Wrong Answer

Solution code:
n = int(input())

def primes(n):
    primfac = {}
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            if d in primfac:
                primfac[d] += 1  # supposing you want multiple factors repeated
            else:
                primfac[d] = 1
            n //= d
        d += 1
    if n > 1:
       primfac[n] = 1
    return primfac


res = 1
cao = primes(n - 1)
for i in cao:
    res *= (cao[i] + 1)
res -= 1

res2 = 0
gan = primes(n)
try:
    if gan[n] == 1:
        res2 = 0
except:
    if len(gan) == 1:
        res2 += list(gan.items())[0][1] - 1
    else:
        for i in gan:
            if (n // i**gan[i]) % i == 1:
                res2 += 1

print(res + res2 + 1)

Submission status: Wrong Answer

Solution code:
N=int(input())
def factors(x):
   t=[]
   for i in range(2, int(x**0.5)+1):
       if x % i == 0:
           t.append(i)
           if x//i!=i:
               t.append(x//i)     
   return t
ans=2+len(factors(N-1))
fac=factors(N)
for i in fac:
    n=N
    while n%i==0:
        n=n//i
    n=n%i
    if n==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

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

ans += len(make_divisors(N-1))-1

for i in make_divisors(N):
    if i == 1:
        continue

    now = N
    while now % i == 0:
        now //= i
    if i in make_divisors(now-1):
        ans += 1

print(ans+1)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = [n]
    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


def main():
    N = int(input())
    n = make_divisors(N)
    m = make_divisors(N - 1)
    answer = m[:] + [N]
    for i in n:
        if i == 2:
            continue
        answer.extend(make_divisors(i - 1))

    answer = set(answer)
    cnt = 0
    for i in answer:
        tmp = N
        while tmp % i == 0:
            tmp //= i
        tmp %= i
        if tmp == 1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
a=int(input())
def div(n):
    div=set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.add(i)
            div.add(n//i)
            if i != n // i:
                div.add(i)
    return div
s=list((div(a)|div(a-1))|div(a+1))
def x(n,k):
  if k==1:
    return False
  else:
    while n>1 and n>k:
      if n%k==0:
        n=n//k
      else:
        n=n%k
    if n==1:
      return True
    else:
      return False
ans=1
for i in s:
  if x(a,i):
    ans+=1
  else:pass
print(ans)

Submission status: Wrong Answer

Solution code:
def check(n, k):
    m = n % k
    if m > 1:
        return 0
    if m == 1:
        return 2
    if m == 0:
        return check(n // k, k)


def main():
    n = int(input())
    c = 1
    for k in range(2, int(n**0.5) + 1):
        c += check(n, k)
    print(c)


if __name__ == '__main__':
    main()

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:
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
        
        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:
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 len(divisors)
N = int(input())
if N == 2:
    print(1)
    quit()
if N == 3:
    print(2)
    quit()
print(make_divisors(N-1)+1)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
def pf(x):
  ret={}
  for i in range(2,int(x**0.5)+1):
    while x%i==0:
      ret[i]=ret.get(i,0)+1
      x//=i
  if x>1:
    ret[x]=1
  return ret

D1=pf(n)
D2=pf(n-1)
ans=0
cur=1
for i in D2.keys():
  cur*=D2[i]+1
ans+=cur

for i in D1.keys():
  if (i**D1[i])**2<=n:
    ans+=1
print(ans)

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 len(divisors)
print(make_divisors(N-1)+1)

Submission status: Wrong Answer

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

def calc(n,x):
    if x==1: return n
    while n>=x:
        if n%x == 0:
            n //= x
        else:
            n %= x
    return n

n = int(input())

div_list = divisor(n)
ans = 0

for div in div_list:
    x = calc(n,div)
    if x==1: ans +=1

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