Problem:


Score : 600 points

Problem Statement

Given is a positive integer N.

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

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

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

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

6

Sample Output 1

3

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

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

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

When K=5: 6 \to 1

When K=6: 6 \to 1

Sample Input 2

3141

Sample Output 2

13

Sample Input 3

314159265358

Sample Output 3

9



Sample input:
6


Sample output:
3

Submission status: Wrong Answer

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

    divisors.sort()
    return divisors

n = int(input())
nl = make_divisors(n)
nl_p = make_divisors(n+1)
nl_m = make_divisors(n-1)
l = sorted(list(set(nl + nl_p+nl_m)))

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())


def factorization_dict(k):
    ret = defaultdict(int)
    i = 2
    while k > 1 and i * i <= k:
        while k % i == 0:
            ret[i] += 1
            k //= i
        i += 1
    if k > 1:
        ret[k] += 1
    return ret


def factorization_list(k):
    ret = []
    i = 2
    while k > 1 and i * i <= k:
        while k % i == 0:
            ret += [i]
            k //= i
        i += 1
    if k > 1:
        ret += [k]
    return ret


fact = factorization_list(n)
fact1 = factorization_dict(n - 1)
print(fact)

s = set()


for i in range(1, pow(2, len(fact))):
    k = 1
    for j in range(len(fact)):
        if (i >> j) & 1:
            k *= fact[j]
    nn = n
    while nn % k == 0:
        nn //= k

    if nn % k == 1:
        s.add(k)

mul = 1
for v in fact1.values():
    mul *= v + 1

print(len(s) + mul - 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

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_list=factorization(N)
b_list=make_divisors(N-1)

cnt = 0
for a in a_list:
    b=a[0]**a[1]
    c=N//b
    if c%b==1:
        cnt+=a[1]+1
    else:
        pass

print(cnt+len(b_list)-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
count = 0
for K in range(2,N+1):
  if N % K == 0:
    N = N/K
  else:
    N = N - K
if N == 1:
  count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import math

input = sys.stdin.readline

N = int(input())
ans = 2
check = []
for i in range(2, N//2+1):
    if N % i == 1:
        check.append(i)
        ans += 1
    elif N % i == 0:
        temp = N
        while temp % i == 0:
            temp = temp // i
        if temp % i == 1 or temp == 0:
            ans += 1
            check.append([i, 'two'])

print(ans)

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

div = factor(n)

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

if not(len(div)==1):
    ans+=1
if len(div)==1:
    ans+=div[0][1]-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)
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 (i-1)%(n//i)==0:
            cnt+=1
print(ans-2+cnt)

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

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

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

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)
def getfact(n):
    ans=[]
    for i in range(2,int(math.sqrt(n))+2):
        if n%i==0:
            a,b=n//i,i
            ans.append(a)
            ans.append(b)
    ans.sort()
    return ans
n=int(sys.stdin.readline())
count=0
temp=n
rem=set()
rem.add(n-1)
vis=defaultdict(int)
countfact(n-1,rem)
for i in rem:
    vis[i]=1

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

#print(count,'count')       
ans=len(rem)+count
if 1 in rem:
    ans-=1
#print(rem,'rem')
#print(ans,'ans')
count,z=1,True
while z:
    a=math.sqrt(n)
    #print(a,'a')
    if a%1==0:
        count+=1
    else:
        z=False
    n=a
print(ans+count)

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

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

for i in range(2**L):
    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 == 0:
            res += 1

print(res + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())


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


factors = factorization(N - 1)
tmp = 1
for prime, power in factors:
    tmp *= power + 1

ans = tmp - 1


divisors = make_divisors(N)
divisors.remove(1)
for d in divisors:
    n = N
    while n % d == 0:
        n //= d
    if n % d == 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

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_list=factorization(N)
b_list=make_divisors(N-1)

cnt = 0
for a in a_list:
    b=a[0]**a[1]
    c=N//b
    if c%b==1:
        cnt+=a[1]+1
    else:
        pass

print(cnt+len(b_list))

Submission status: Wrong Answer

Solution code:
N = int(input())

cnt = 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)

    # divisors.sort()
    return divisors
res1 = sorted(make_divisors(N))
res1 = res1[1: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)

print(cnt)

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 % num == 0:
        ans += 1
    else:
        if tmp % num == 1:
            ans += 2

    num += 1

num -= 1

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


print(ans)

Submission status: Wrong Answer

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

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


n=int(input())
soin=factorization(n)
minus=factorization(n-1)
# print(soin)
# print(minus)
d={}
for i in range(len(soin)):
    d[soin[i][0]]=soin[i][1]
# print(d)
ans=0
tmp=1
for i in range(len(minus)):
    if minus[i][0]!=1:
        tmp*=minus[i][1]+1
tmp-=1
ans+=tmp
print(ans+2)

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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(readline())
print(len(set(make_divisors(n) + make_divisors(n - 1))) - 2)

Submission status: Wrong Answer

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


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


fact = factorize(K-1)
ans = 1

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

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

Submission status: Wrong Answer

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

def kazu(j):
    nu = make_divisors(j-1)
    return nu
from collections import deque
que = deque([N])
count = 1
ans = set()
while que:
    nn = que.popleft()
    yak = make_divisors(nn)
    tem = kazu(nn)
    for z in tem:
        ans.add(z)
    if len(yak) >2:
        for k in yak:
            if nn%k ==1:
                ans.add(k)
print(len(ans)+1)

Submission status: Wrong Answer

Solution code:

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

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

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


def resolve():
    N = int(input())
    ys= set(make_divisors(N))
    ys2= set(make_divisors(N-1))
    x =set([i for i in ys if check(N,i)])

    print(len(x | ys2))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

    divisors.sort()
    return divisors

def 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_list=factorization(N)
b_list=make_divisors(N-1)

cnt = 0
for a in a_list:
    b=a[0]**a[1]
    c=N%b
    if c%b==1:
        cnt+=a[1]+1
    else:
        pass

print(cnt+len(b_list))

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 % num == 0:
        ans += 1
    else:
        if tmp % num == 1:
            ans += 2

    num += 1

num -= 1




print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
rn = int(math.sqrt(n) // 1)
li = []
for i in range(2, rn+1):
	if n % i == 0:
		li.append(i)
ans = 0
for i in range(len(li)):
	m = n
	while m % li[i] == 0:
		m //= li[i]
	if m % li[i] == 1:
		ans += 1
#print(ans)
rm = int(math.sqrt(n-1)//1)
cnt = 0
for i in range(2, rm+1):
	#print(i)
	if (n-1) % i == 0:
		cnt += 1
#print(cnt)
ans += (2*cnt+2)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def factorize(n):
    b = 2
    fct = [(1,1)]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
ans = 1
ls = factorize(n-1)
for num,cnt in ls:
    if num !=1:
      ans *= (cnt+1)
print(ans+1)

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)
for c in ctres.keys():
    t = N
    while t % c == 0:
        t /= c
    if (t - 1) % c == 0:
        res += 1
print(res)

Submission status: Wrong Answer

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

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

def make_divisors(n):
    divisors = []
    for i in range(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

ans.extend(make_divisors(n-1))
ans.append(n)
ans.append(n-1)
answer = list(set(ans))
def n_1(n):
    if n == 2:
        return 1
    else:
        return 0
print(len(answer)-n_1(n))

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

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_list=factorization(N)
b_list=make_divisors(N-1)

cnt = 0
for a in a_list:
    b=a[0]**a[1]
    c=N%b
    if c%b==1:
        cnt+=a[1]
    else:
        pass

print(cnt+len(b_list))

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    ans = []

    def trial_division(n):
        divs = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                if i != 1:
                    divs.append(i)
                if i != n//i:
                    divs.append(n//i)
        return divs
    ans = trial_division(N-1) + [2] + [N]
    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

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

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

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


def resolve():
    N = int(input())
    ys= make_divisors(N)
    ys2= set(make_divisors(N-1))
    x =set([i for i in ys if check(N,i)])

    print(len(x | ys2))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 2
for i in range(2,int((n-1) ** 0.5) + 2):
    if (n-1) % i == 0:
        #print(i)
        ans += 1
        if i ** 2 < n-1:
            ans += 1
        else:
            if i ** 2 > n-1:
                ans -= 1
            break
#print(ans)

for i in range(2,int(n ** 0.5) + 2):
    if n % i == 0:
        nt = n
        while (nt % i == 0):
            nt = nt // i
        if nt % i == 1:
            ans += 1
        if i ** 2 < n:
            nt = n
            it = n - i
            while (nt % it == 0):
                nt = nt // it
            if nt % i == 1:
                ans += 1            
print(ans)

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 % num == 0:
        ans += 1
    else:
        if tmp % num == 1:
            ans += 2

    num += 1

num -= 1

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


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()

from collections import defaultdict
import fractions # version 3.4
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def lcm(*numbers):
    return reduce(lambda x,y: (x * y) // fractions.gcd(x, y), numbers, 1)


def factorize(n):
    fct = defaultdict(lambda: 0)
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct[b] = e
        b, e = b + 1, 0
    if n > 1:
        fct[n] = 1
    return fct


res1 = 1

for i in factorize(n-1).values():
    res1 *= (i+1)

# print(factorize(n-1))
# print( gcd(*factorize(n).values()))
print(res1 + gcd(*factorize(n).values()))

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 * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

yakusu = prime_factorize(n)
print(int(len(yakusu)*(len(yakusu)-1)/2))

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[:]
    cnt = len(answer)
    for i in n:
        tmp = N
        while tmp % i == 0:
            tmp //= i
        if tmp % i == 1:
            cnt += 1
            answer.append(i)
    answer.sort()
    print(cnt)


if __name__ == '__main__':
    main()

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)-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:
from math import ceil, sqrt

def main():
    n = int(input())
    c = 2 + (int(sqrt(n))**2 == n) + (int(sqrt(n - 1))**2 == (n - 1))
    for k in range(2, ceil(sqrt(n - 1))):
        m = n % k
        if m > 1:
            continue
        elif m == 1:
            c += 2
        else:
            p = n // k
            while p % k == 0:
                p //= k
            if p % k == 1:
                c += 1
    print(c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import sqrt
n=int(input())
c=2
for i in range(2,int(sqrt(n))+1):
    x=i
    y=n//i
    n1=n
    while(n1%x==0):
        n1//=x
    c1=n1%x
    if(c1==1):
        c+=1
    elif(n1>x and (x-c1)==1):
        c+=1
    n1=n
    while(n1%y==0):
        n1//=y
    c1=n1%y
    if(c1==1):
        c+=1
    elif(n1>y and (y-c1)==1):
        c+=1
print(c)

Submission status: Wrong Answer

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

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

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

for i in range(2**L):
    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
    if tmp == 0:
        res += 1
    else:
        for k in range(1, tmp2 + 1):
            if tmp2 // k != 0:
                continue
            if tmp // tmp3 ** k == 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
for i in divlist:
    if i % N == 1:
        count += 1
print(count + len(make_divisors(N-1)))

Submission status: Wrong Answer

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

N = int(input())

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

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

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

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

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

Solution code:
N = int(input())

divisor = set([N, N - 1])
x = N
for i in range(2, int(x ** 0.5) + 1):
    if x % i == 0:
        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:
def divisors(n):
    d=[]
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            d.append(i)
            if i!=n//i:
                d.append(n//i)
    d.sort()
    return d
i=int(input())
a=divisors(i-1)
if 2 not in a:
    a.insert(0,2)
if i>2:
    a.append(i-1)
if i>1:
    a.append(i)
print(len(a))

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

div = factor(n)

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

if not(len(div)==1 and div[0][1]==1):
    ans+=1

print(ans)