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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
for i in range(2,min(n-1,int(n**.5)+1)):
# for i in range(2,n*+1):
  if n % i == 0:
    tmp = n

    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1

    if n //i == i or n //i == n or n // i == n-1:continue

    tmp = n; i = n // i
    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1

  elif (n-1) % i == 0:
    if (n-1)//i != i and  (n-1) //i != n and (n-1) // i != n-1:ans += 2
    else: ans += 1

if n != 1:ans += 2
else: ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

m = 2
n1 = n - 1
while m * m <= n1:
    ans += n1 % m == 0
    m += 1
print(ans)

Submission status: Wrong Answer

Solution code:

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


def calc(n):
    cnt = 3
    for k in range(2, n // 2):
        if judge(n, k) == 1:
            cnt += 1
    return cnt


def cal(n):
    cnt = 3
    for d in range(3, 10):
        if n % d <= 1:
            k = n // d
            if judge(k) == 1:
                cnt += 1

    for k in range(2, n // 10):
        if judge(n, k) == 1:
            cnt += 1
    return cnt


def main():
    N = int(input())
    s = {}
    cnt = 0

    print(calc(N))


main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    n = int(input())
    ans = set([n])
    ans |= set(make_divisors(n))
    ans |= set(make_divisors(n-1))
    ans -= set([1])
    print(len(ans))

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math

n=input()
res=2

if n==2:
    print 1
    exit(0)
if n==3:
    print 2
    exit(0)
for i in xrange(2, int(math.sqrt(n)+1)+1):
    k=n
    while k>1:
        if k%i==0:
            k=k/i
        else:
            k=k%i
            break
        
    if k==1:
        res+=1

for i in xrange(2, int(math.sqrt(n)+1)+1):
    if (n-1)%i==0:
        res+=1

print res

Submission status: Wrong Answer

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

# 2とNは必ず含まれる
k = {2, n}

# N-1の約数
for i in range(1, int(math.sqrt(n)) + 1):
    if (n-1) % i == 0:
        k.add(i)
        k.add((n-1)//i)
    if i > 1 and n % i == 0:
        tmp = n // i
        while True:
            tmp = tmp // i
            if tmp % i != 0:
                break
        if (tmp - 1) % i == 0:
            k.add(i)

# べき乗数
for a in range(2, 100):
    root = round(n ** (1/a))
    if root ** a == n:
        k.add(root)
    if root < 2:
        break

k.remove(1)
print(len(k))

Submission status: Wrong Answer

Solution code:
import math

def divisors(n):
    div = [n]
    for i in xrange(2,int(math.sqrt(n))+1):
        if n%i == 0:
            div.append(i)
            div.append(n/i)
    return div

n = int(raw_input())
ndiv = set(divisors(n))
mdiv = set(divisors(n-1))
count = 0
for x in ndiv:
    for k in xrange(1,31):
        if x**k > n:
            break
        if (n/x**k)%x == 1:
            count += 1
            #print x
            break
count += len(mdiv)
print count

Submission status: Wrong Answer

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

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

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

print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
for i in range(2,min(n-1,int(n**.5)+1)):
# for i in range(2,n*+1):
  if n % i == 0:
    tmp = n

    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1
  
    tmp = n; i = n // i
    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1

  elif (n-1) % i == 0:ans += 2

if n != 1:ans += 2
else: ans += 1
print(ans)

Submission status: Wrong Answer

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

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


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

#print(yakusuu(N))
#print(yakusuu(N-1))
N_yaku = yakusuu(N)
N_1_yaku = yakusuu(N-1)
if(len(N_yaku) != 1):
    del N_yaku[0]
if(len(N_1_yaku) != 1):
    del N_1_yaku[0]
#print(N_yaku)
#print(N_1_yaku)
counter = 0
#N-1の約数であるとき→Nの約数でなければOK
for i in N_1_yaku:
    #print(i)
    #print(i in N_yaku)
    if( (i in N_yaku) == False ) :
        #print('false_hit')
        counter += 1

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



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

print(counter)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

Submission status: Wrong Answer

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import sqrt
input = stdin.readline

N = int(input())
cnt = 2

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

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


for i in range(2, int(sqrt(N)) + 1):
    for j in range(40):
        if pow(i, j + 1) + pow(i, j) == N:
            cnt += 1


print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
from math import sqrt
ans = 0
for i in range(2, int(sqrt(N-1)) + 1):
    if ( N - 1) % i == 0: ans += 1

print(min(N-1, 2 * ans + 3))

Submission status: Wrong Answer

Solution code:
import math


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


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

Submission status: Wrong Answer

Solution code:
#F
n = int(input())
root_n = int(n**0.5)
ans = 2
for k in range(2,root_n+1):
    if n%k==0 and k!=2:ans +=1
    n_k = n
    ama = n
    while n_k%k == 0:
        if n_k%k==0 and k!=2:ans +=1
        n_k = n_k//k
    if n_k%k==1:
        ans+=1
        

if n > 4:
    print(ans)
else:
    print(n-1)

Submission status: Wrong Answer

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

n = int(input())

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

ans = set()

a = prime_factorize(n)

from collections import Counter

c = Counter(a)

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

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

    divisors.sort()
    return divisors

d = make_divisors(n - 1)

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

ans.add(n)

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

print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
for K in range(1, int(N**0.5)+1):
    if N % K == 0:
        if 1 < K:
            tmp = N
            while tmp % K == 0:
                tmp //= K

            if tmp == 1:
                ans += 1
            else:
                if tmp % K == 1:
                    ans += 1
        if K != N // K:
            tmp = N // K

            if 1 < K:
                while tmp % K == 0:
                    tmp //= K
            if tmp == 1:
                ans += 1
            else:
                if tmp % K == 1:
                    ans += 1
    else:
        if N % K == 1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math


N = int(input())

nn = int(math.sqrt(N))

ans = 0
for x in range(2,nn+1):

    if N % x > 1:
        continue

    if N % x == 1:
        ans += 1
        continue
    
    tmp = N
    while True:
        tmp = tmp / x
        if tmp % x  == 1:
            ans += 1
            break
        elif tmp == x :
            ans += 1
            break
        elif tmp % x >= 1:
            break

print(ans+2)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n=int(input())
ans=2
for i in range(2,int(sqrt(n))+1):
    if n%i==1:
        ans+=1
        break
    while n%i==0:
        n//=i
    if n==1:
        ans+=1
    else:
        if n%i==1:
            ans+=1
print(ans)

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
a=set()
a.add(1)
a.add(N)
a.add(N-1)
b=factorization(N-1)
for B in b:
    a.add(B[0])
print(len(a))

Submission status: Wrong Answer

Solution code:
n = int(input())
count = [2,n,n-1]
for i in range(3,10):
    a = n
    while a%i == 0:
        a//= i
    if (a-1)%i == 0:
        if not i in count:
            count.append(i)
for i in range(2,int((n-1)**0.5)+1):
    if (n-1)%i == 0:
        if not i in count:
            count.append(i)
        if not (n-1)//i in count:
            count.append((n-1)//i)
        


print(len(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-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
elif len(div)==1:
    k=div[0][1]
    cnt=0
    while(k>2):
        k//=2
        cnt+=1
    if k==0:
        ans+=cnt
    

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
n = int(input())
if n == 2:
    print(0)
elif n == 3:
    print(2)
elif n == 4:
    print(3)
else:
    count = 2
    check_list = make_divisors(n-1)
    count += len(check_list)
    temp_n = str(n)
    suma = 0
    for i in range(len(temp_n)):
        suma += int(temp_n[i])
    if suma % 3 == 1:
        count += 1

    """
    for k in [3]:
        temp_n = n
        while(True):
            if temp_n % k == 0:
                temp_n = temp_n // k
            else:
                temp_n = temp_n - k
                if temp_n <= 0:
                    break
            if temp_n == 1:
                count += 1
                break
    """
    print(count)

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)
    print(ans+1)

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

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)

f = True
ans = 1
c = 2
for i in P.keys():
  ans *= P[i] + 1
  if P[i] / 2 != P[i] // 2:
    f = False
  c = min(c, P[i] // 2)
ans += 1
if f:
  ans += c
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
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())
x = factorization(n)
d = int(x[len(x)-1][0]**x[len(x)-1][1])
b = int(n/d)
ans = 0
for i in range(b,int(np.log10(d))+2,b):
    while(i<d):
        if d%i == 1:
            ans+=1
        i*=i

print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
k = int(input())
cnt = 0
k = k-1

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(k)+1)

Submission status: Wrong Answer

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

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

cnt = 0
for v in sorted(list(set(kouho)))[1:]:
    K = v
    tmp_N = N_tmp
    if K <= 1: continue
    print(tmp_N, K)
    while tmp_N >= K:
        if tmp_N % K == 0:
            tmp_N = tmp_N // 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())

nn = int(math.sqrt(N))

ans = 0
for x in range(2,nn+1):

    if N % x > 1:
        continue

    if N % x == 1:
        ans += 1
        continue
    
    tmp = N
    while True:
        tmp = tmp / x
        if tmp % x  == 1:
            ans += 1
            break
        elif tmp == x :
            ans += 1
            break
        elif tmp % x >= 1:
            break

print(ans+3)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
if n == 2:
	print(1)
else:
	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(m, li[i])
	#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 = 0

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

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

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

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

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Wrong Answer

Solution code:
def factor(num):
    ls = []
    fac = 1
    for i in range(2, ceil(sqrt(num))):
        if num % i == 0:
            counter = 0
            while num % i == 0:
                num //= i
                counter += 1
            ls.append(counter)
        if num == 1:
            break
    else:
        fac = 2
    
    for e in ls:
        fac *= (e+1)

    return (fac) //2
            

from math import sqrt, ceil

N = int(input())

ans = 1

for K in range(2, ceil(sqrt(N))):
    N_tmp = N
    while N_tmp % K == 0:
        N_tmp //= K
    if N_tmp % K == 1:
        ans += 1



print(ans + factor(N-1))

Submission status: Wrong Answer

Solution code:
N = int(input())
from math import sqrt
ans = 0
for i in range(2, int(sqrt(N-1)) + 1):
    if ( N - 1) % i == 0: ans += 1

print(2 * ans + 3)

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
    cntone = 0
    for prime in prime_list:
        count = 1
        while num % prime == 0:
            num //= prime
            count += 1
        if count != 1: cntone += 1
        divisor_num *= count

    if num != 1:
        divisor_num *= 2

    return divisor_num


s = search_divisor(n-1) # ほんとは1を除くので-1、ただ自身を結局足すので
# d = 1 if n % 2 == 0 else 0
print(s + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
n = int(input())
if n == 2:
    print(0)
elif n == 3:
    print(2)
elif n == 4:
    print(3)
else:
    count = 2
    check_list = make_divisors(n-1)
    count += len(check_list)
    temp_n = str(n)
    suma = 0
    for i in range(len(temp_n)):
        suma += int(temp_n[i])
    if suma % 3 == 0:
        count += 1
        
    """
    for k in [3]:
        temp_n = n
        while(True):
            if temp_n % k == 0:
                temp_n = temp_n // k
            else:
                temp_n = temp_n - k
                if temp_n <= 0:
                    break
            if temp_n == 1:
                count += 1
                break
    """
    print(count)

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


from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

for i in factors(n):
    if (n // i) % i == 1 or (n // i) % i == 0:
        res2 += 1

print(res + res2)

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 or (t - 1) % c == 0:
        res += 1
print(res)

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

for i in range(2, int(N**0.5)+1):
    M = N
    while M >= i:
        if M % i == 0:
            M //= i
        else:
            M -= i
    if M == 1:
        count += 1
print(count)

Submission status: Wrong Answer

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

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


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

#print(yakusuu(N))
#print(yakusuu(N-1))
N_yaku = yakusuu(N)
N_1_yaku = yakusuu(N-1)
del N_yaku[0]
del N_1_yaku[0]
#print(N_yaku)
#print(N_1_yaku)
counter = 0
#N-1の約数であるとき→Nの約数でなければOK
for i in N_1_yaku:
    #print(i)
    #print(i in N_yaku)
    if( (i in N_yaku) == False ) :
        #print('false_hit')
        counter += 1

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



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

print(counter)

Submission status: Wrong Answer

Solution code:

def 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:
        return True
    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()