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: Accepted

Solution code:
N = int(input())

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

if N <= 10**6:
    ans = 0
    for i in range(2, N + 1):
        if isOk(i):
            ans += 1
    print(ans)
    exit()

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
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)
    # divisors.sort(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)

ans += len([d for d in divN if not d in V])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

cnt = 0

def check(d):
    tmp = n
    while tmp % d == 0:tmp //= d
    tmp %= d
    return tmp == 1

d = 1
while d * d <= n:
    if n % d != 0:
        d+=1
        continue
    if d != 1:
        cnt += check(d)
    if n // d > d:
        cnt += check(n // d)
    d += 1

n -= 1
d = 1
while d * d <= n:
    if n % d != 0:
        d+=1
        continue
    if d != 1:
        cnt += 1
    if n // d > d:
        cnt += 1
    d += 1

print(cnt)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    def PrimeDecomposition(N):
        ret = {}
        n = int(N ** 0.5)
        for d in range(2, n + 1):
            while N % d == 0:
                if d not in ret:
                    ret[d] = 1
                else:
                    ret[d] += 1
                N //= d
            if N == 1:
                break
        if N != 1:
            ret[N] = 1
        return ret

    N = int(input())
    n = int(N**0.5)

    ans = 0
    for k in range(2, n+1):
        M = N
        while M >= k:
            if M%k==0:
                M //= k
            else:
                M %= k
        if M == 1:
            ans += 1

    prime = PrimeDecomposition(N-1)
    ans2 = 1
    for p in prime:
        ans2 *= (prime[p] + 1)
    print(ans + ans2//2 + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

l1 = []
for n in range(1,int(N**0.5)+1):
    if N%n==0:
        l1.append(n)
        l1.append(N//n)
l1 = list(set(l1))
l1.sort()

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

l1 = l1[1:]
l2 = l2[1:]

ans = l2

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

for i in l1:
    if cal(N,i)==1:
        ans.append(i)

ans = len(set(ans))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 1
pr = []
if n == 2:
  print(1)
  exit()
if n == 3:
  print(2)
  exit()
for i in range(1,int(n**0.5)):
  if (n-1)%i == 0:
    pr.append((n-1)//i)
ans += len(pr)
for i in range(2,int(n**0.5+2)):
  t = n
  while t > i:
    if t%i:
      t %= i
    else:
      t //= i
  if t == 1 or t == i:
    ans += 1
if int(n**0.5+0.5)**2 == n:
  ans -= 1
print(ans)

Submission status: Accepted

Solution code:
def f(x):
    s=set()
    for i in range(1,int(x**(0.5))+6):
        if x%i==0: s.add(i);s.add(x//i)
    return s 


ans=set()
n=int(input())
ans=f(n-1)
ans1=f(n)
ans1.remove(1)

for x in ans1:
    p=n
    while p>=x:
        if p%x==0: p//=x
        else: p%=x
    if p==1: ans.add(x)

if 1 in ans: ans.remove(1)
print(len(ans))

Submission status: Accepted

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

x=int(input())

DIV=[]

for i in range(1,int(sqrt(x))+2):
    if x%i==0:
        DIV.append(i)
        DIV.append(x//i)

ANS=[]
for d in DIV:
    if d==1:
        continue
    k=x
    while k%d==0:
        k//=d
    if k%d==1:
        ANS.append(d)

t=x-1
for i in range(1,int(sqrt(t))+2):
    if t%i==0:
        ANS.append(i)
        ANS.append(t//i)

print(len(set(ANS))-1)

Submission status: Accepted

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

x=int(input())

DIV=[]

for i in range(1,int(sqrt(x))+2):
    if x%i==0:
        DIV.append(i)
        DIV.append(x//i)

ANS=[]
for d in DIV:
    if d==1:
        continue
    k=x
    while k%d==0:
        k//=d
    if k%d==1:
        ANS.append(d)

t=x-1
for i in range(1,int(sqrt(t))+2):
    if t%i==0:
        ANS.append(i)
        ANS.append(t//i)

print(len(set(ANS))-1)

Submission status: Accepted

Solution code:
n = int(input())
count = 1
for i in range(int(n ** 0.5)):
    test = i + 1
    n2 = n
    if test == 1:
        continue
    while n2 % test == 0:
        n2 //= test
    else:
        n2 %= test
    if n2 == 1:
        count += 1
n3 = n - 1
a = []
for i in range(1, int(n3 ** 0.5) + 1):
    if n3 % i == 0:
        temp = n3 // i
        if temp > int(n ** 0.5):
            a.append(temp)
count += len(a)
print(count)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 12
# 12 6 3 1
# 12 4 1

def check(d, n):
    if d == 1: return False
    while n % d == 0:
        n //= d
    return n % d == 1

n = ni()
ans = 0
for d in range(1, n+1):
    if d*d > n: break
    if n % d == 0:
        if check(d, n):
            ans += 1
        if d * d < n and check(n//d, n):
            ans += 1

for d in range(1, n):
    if d*d > n-1: break
    if (n-1) % d == 0:
        if d != 1:
            ans += 1
        if d * d < n-1 and n//d != 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

N = int(read())


def divisor(N):
    x = np.arange(1, 10 ** 6 + 1, dtype=np.int64)
    div = set(x[N % x == 0])
    return div | set(N // x for x in div)


cand = divisor(N) | divisor(N - 1)


def test(N, K):
    if K == 1:
        return False
    while N % K == 0:
        N //= K
    return N % K == 1


answer = sum(test(N, d) for d in cand)
print(answer)

Submission status: Accepted

Solution code:
def divisor(n):
    res = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            res.append(i)
            if i**2 == n:
                continue
            res.append(n//i)
    return res
n = int(input())
res = divisor(n)
ans = len(divisor(n-1))-1
for r in res:
    if r == 1:
        continue
    tmp = n
    while tmp%r==0:
        tmp//=r
    if tmp%r == 1:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

import sympy
N = I()
a = sympy.divisor_count(N - 1)

A = sympy.divisors(N)

cnt = 0
for i in range(1, len(A) // 2 + 1):
    x = A[i]
    y = A[-i - 1]
    while y > x:
        if (y - 1) % x == 0:
            cnt += 1
            break
        elif y % x == 0:
            y //= x
        else:
            break
    if y == x:
        cnt += 1

ans = a - 1 + cnt + 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

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

ans = 0

def factorization(n):
  lis = []
  if n % 2 == 0:
    c = 0
    while n%2 == 0:
      n //= 2
      c += 1
    lis.append([2, c])
  k = 3
  while k*k <= n:
    if n%k == 0:
      c = 0 
      while n%k == 0:
        n //= k
        c += 1
      lis.append([k, c])
    else:
      k += 2
  if n > 1:
    lis.append([n, 1])
  return lis

list1 = factorization(N-1)
ans1 = 1
for k in range(len(list1)):
  ans1 *= list1[k][1]+1
ans += ans1-1

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

list2 = factorization(N)
factorlist = [1]
for l in range(len(list2)):
  list3 = []
  for j in range(list2[l][1]):
    for k in range(len(factorlist)):
      list3.append(factorlist[k]*list2[l][0]**(j+1))
  factorlist += list3
factorlist = factorlist[1:-1]
ans += 1
for item in factorlist:
  if operation(item):
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from sympy import divisors
N = int(input())
ans = len(divisors(N-1))-1
lis = divisors(N)
for n in lis:
    G = N
    if n==1:
        continue
    while G%n==0:
        G //= n
    if G%n==1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
if n == 2:
    print(1)
elif n == 3:
    print(2)
else:
    #print(make_divisors(n-1))
    print(len(make_divisors(n-1))+1)

Submission status: Runtime Error

Solution code:
import math
def prime_factorize(n):
    a = [n]
    for i in range(2, math.floor(n ** 0.5) + 1):
        if n % i == 0:
            a.append(i)
            if n // i != i:
                a.append(n // i)
    return a

N = int(input())
prime_n = prime_factorize(N)
prime_n_1 = prime_factorize(N - 1)

ans = 0
for i in prime_n:
    n = copy.deepcopy(N)
    while (n % i) == 0:
            n = n // i
    if (n % i) == 1:
        ans += 1
ans += len(prime_n_1)
print(ans)

Submission status: Runtime Error

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

N = int(input())
prime_n = prime_factorize(N)
prime_n_1 = prime_factorize(N - 1)

ans = 0
for i in prime_n:
    n = copy.deepcopy(N)
    while (n % i) == 0:
            n = n // i
    if (n % i) == 1:
        ans += 1
ans += len(prime_n_1)
print(ans)

Submission status: Runtime Error

Solution code:
import sympy

n = int(input())

tmp = n - 1
ret = len(sympy.divisors(tmp)) - 1

tmplen = sympy.divisors(n)

for item in tmplen:
    if item == 1:
        continue
    val = n
    while True:
        if val % item == 0:
            val = val // item
        else:
            if val % item == 1:
                ret += 1
            break

print(ret)

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    def divisor(n):
        res = []
        for i in range(1, int(np.sqrt(n)) + 1):
            if n % i == 0:
                res.append(i)
                j = n // i
                if j != i:res.append(j)
        res.sort(reverse = True)
        return res[::-1]
    n = int(input())
    div1 = divisor(n - 1)
    div2 = divisor(n)
    ans = len(div1) - 1
    for d in div2:
        if d == 1: continue
        nn = n
        while nn % d == 0:
            nn //= d
        if nn % d == 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    def divisor(n):
        res = []
        for i in range(1, int(np.sqrt(n)) + 1):
            if n % i == 0:
                res.append(i)
                j = n // i
                if j != i:res.append(j)
        res.sort(reverse = True)
        return res[::-1]
    n = int(input())
    div1 = divisor(n - 1)
    div2 = divisor(n)
    ans = len(div1) - 1
    for d in div2:
        if d == 1: continue
        nn = n
        while nn % d == 0:
            nn //= d
        if nn % d == 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())


def divs(x):
    out = []
    num = 1
    while num < np.sqrt(x) + 0.01:
        if x % num == 0:
            if num == x//num:
                out.append(num)
            elif num < x//num:
                out.append(num)
                out.append(x//num)
        num += 1
    return sorted(out)[1:]


ans = set()


divs_n = divs(n)

for div in divs_n:
    ncp = n
    if (ncp - 1) % div == 0:
        ans.add(div)
        continue
    while ncp % div == 0:
        ncp //= div
        if (ncp-1) % div == 0:
            ans.add(div)
            break


divs_mk = divs(n-1)
for div in divs_mk:
    if div == 1:
        continue
    ans.add(div)

print(len(ans))

Submission status: Runtime Error

Solution code:
import sympy
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


L1 = factorization(N - 1)
s = 1
# print(L1)
for [a, b] in L1:
    s *= (b + 1)
# print(s)
# print(set(sympy.divisors(N))-{1})
for i in set(sympy.divisors(N))-{1}:
    temp = N
    while temp % i == 0:
        temp //= i
    if (temp-1) % i == 0:
        s += 1
s -= 1
print(s)

Submission status: Runtime Error

Solution code:
from sympy import divisors

n = int(input())

a = len(divisors(n-1)[1:])

d = divisors(n)
for dd in d[1:]:
    nn = n
    while nn % dd == 0:
        nn = nn // dd
    if nn % dd == 1:
        a += 1

print(a)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
ABC = np.zeros((N, 3))
for i in range(N):
    ABC[i][0], ABC[i][1], ABC[i][2] = map(int, input().split())
DEF = np.zeros((M, 3))
for i in range(M):
    DEF[i][0], DEF[i][1], DEF[i][2] = map(int, input().split())

# 座標圧縮
x_co = {-10**9-1, 10**9+1}
y_co = {-10**9-1, 10**9+1}
for i in range(N):
    x_co.add(ABC[i][0])
    x_co.add(ABC[i][1])
    y_co.add(ABC[i][2])
for i in range(M):
    x_co.add(DEF[i][0])
    y_co.add(DEF[i][1])
    y_co.add(DEF[i][2])

x_co = np.array(sorted(list(x_co)))
y_co = np.array(sorted(list(y_co)))
xL = len(x_co) - 1
yL = len(y_co) - 1
x_co_d = {x_co[i]: i for i in range(xL+1)}
y_co_d = {y_co[i]: i for i in range(yL+1)}

# 柵の存在
s_ex_tate = np.zeros((yL+1, xL))
s_ex_yoko = np.zeros((xL+1, yL))
for i in range(N):
    a = x_co_d[ABC[i][0]]
    b = x_co_d[ABC[i][1]]
    c = y_co_d[ABC[i][2]]
    s_ex_tate[c][a:b] = 1
for i in range(M):
    d = x_co_d[DEF[i][0]]
    e = y_co_d[DEF[i][1]]
    f = y_co_d[DEF[i][2]]
    s_ex_yoko[d][e:f] = 1

# 初期位置
for i in range(xL):
    if x_co[i+1] > 0:
        xf = [i]
        break
    if x_co[i+1] == 0:
        xf = [i, i+1]
        break
for i in range(yL):
    if y_co[i+1] > 0:
        yf = [i]
        break
    if y_co[i+1] == 0:
        yf = [i, i+1]
        break

def sq(x, y):
    return int((x_co[x+1]-x_co[x]) * (y_co[y+1]-y_co[y]))

# 探索
Q = []
# houmon = [[False] * yL for _ in range(xL)]
houmon = np.zeros((xL, yL))
ans = 0
is_inf = False
for x in xf:
    for y in yf:
        houmon[x][y] = 1
        Q.append((x, y))

while Q:
    x, y = Q.pop()
    if x in [0, xL-1] or y in [0, yL-1]:
        is_inf = True
        break
    ans += sq(x, y)
    if (not houmon[x-1][y]) and (not s_ex_yoko[x][y]):
        houmon[x-1][y] = True
        Q.append((x-1, y))
    if (not houmon[x][y-1]) and (not s_ex_tate[y][x]):
        houmon[x][y-1] = True
        Q.append((x, y-1))
    if (not houmon[x+1][y]) and (not s_ex_yoko[x+1][y]):
        houmon[x+1][y] = True
        Q.append((x+1, y))
    if (not houmon[x][y+1]) and (not s_ex_tate[y+1][x]):
        houmon[x][y+1] = True
        Q.append((x, y+1))
    
if is_inf:
    print('INF')
else:
    print(ans)

Submission status: Runtime Error

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

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k

for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        ans.add(k)
        ans.add((N-1)//k)
    if N%k==0:
        if check(N, k):
            ans.add(k1)
        if check(N, N//k):
            ans.add(k2)

ans.remove(1)
print(len(ans))

Submission status: Runtime Error

Solution code:

def solve1(n):
    # n = k ^ a
    res = []
    for i in xrange(1, 100):
        u = int(pow(n, 1.0 / i) + 0.1)
        if u ** i == n:
            res.append(u)
    return set(res)

def solve2(n):
    # n = a * k + 1
    m = n - 1

    i = 1
    res = set()
    while i * i <= m:
        if m % i == 0:
            res.add(i)
            res.add(m / i)
        i += 1
    return res ^ set([1])

def solve3(n):
    i = 2
    res = set()
    while i * i <= n:
        if n % i == 0:
            m = n / i
            while m and m % i == 0:
                m /= i
            if m % i == 1:
                res.add(i)
        i += 1
    return res

def brute_force(n):
    res = []
    for i in xrange(2, n + 1):
        m = n
        while m % i == 0:
            m /= i
        m %= i
        if m == 1:
            res.append(i)
    # print res
    return len(res)

def solve(n):
    s1 = solve1(n)
    s2 = solve2(n)
    s3 = solve3(n)
    # print sorted(s1 | s2 | s3)
    return len(s1 | s2 | s3)

assert solve(6) == 3
assert solve(3141) == 13
assert solve(314159265358) == 9

assert solve(10 ** 12)

import random
for i in xrange(100):
    n = random.randint(1, 1000)
    assert brute_force(n) == solve(n)

n = int(raw_input())
print solve(n)

Submission status: Runtime Error

Solution code:
import numpy as np

def divisors(N):
    return sorted(sum(([*{n, N // n}] for n in range(1, int(N ** 0.5) + 1) if not N % n), []))

def prime_factorize_dict(n):
    d = dict()
    while not n & 1:
        d[2] = d.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            d[f] = d.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n] = d.get(n, 0) + 1
    return d

N = int(input())
count = 0
for n in divisors(N)[1:]:
    M = N
    while not M % n:
        M //= n
    count += M % n == 1
fact_Nm1 = np.array(list(prime_factorize_dict(N - 1).values()), dtype=np.int32)
print(count + np.prod(fact_Nm1 + 1) - 1)

Submission status: Runtime Error

Solution code:
n, k, c = input().split()
k = int(k)
n = int(n)
c = int(c)
s = input()
l = [i + 1 for i, x in enumerate(s) if x == 'o']

# print(l)

if k == 1:
    if len(l) == 1:
        print(l[0])
    else:
        exit(0)

s = 0
n_s = 0
e_flag = True

f = []

for i in l:
    if i <= s:
        continue
    n_s += 1
    f.append(i)
    if n_s == k:
        e_flag = False
        break
    s = i + c

# print(f)

if e_flag:
    exit(0)

b = []
n_s = 0
s = 2000010

for i in reversed(l):
    if i >= s:
        continue
    n_s += 1
    b.append(i)
    if n_s == k:
        break
    s = i - c

# print(b)

r = list(set(f) - (set(f) - set(b)))
for i in sorted(r):
    print(i)

Submission status: Runtime Error

Solution code:
from math import gcd

print(gcd(120, 24))

Submission status: Runtime Error

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))
def prime_decomposition(n):
    i = 2
    table = []
    while i*i <= n:
        while n%i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table
def prime_decomposition2(n):
    i = 2
    table = defaultdict(int)
    while i*i <= n:
        while n%i == 0:
            n //= i
            table[i] += 1
        i += 1
    if n > 1:
        table[n] += 1
    return table
def make_divisor(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())
list_pd1 = make_divisor(N)
list_pd1.sort()
dict_pd2 = prime_decomposition2(N-1)
#print(N, ':', list_pd1)
#print(N-1, ':', dict_pd2)

cnt = 1

# -1 nohou
for val in dict_pd2.values():
    cnt *= (val+1)
cnt -= 1
#print(cnt)

for k in list_pd1[1:]:
    #print('k:', k)
    sN = N
    while sN >= k:
        if sN%k==0:
            sN //= k
        else:
            sN %= k
    if sN == 1:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
ans=0
N=input()
for K in range(2,N+1):
    n=N
    while n>=K:
        if n%K==o:
            n=n/K
        else:
            n=n-K
    if n=1:
        ans=ans+1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

m = 0
for i in range (2 , N + 1):
    if N % i == 1:
        m = m + 1
    else N % i == 0:
        while N % i == 0:
            N //= i
        if N % i == 1:
            m = m + 1

print ( m )

Submission status: Runtime Error

Solution code:
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 sorted(divisors) 
n = int(input())
ans = len(divisors(n-1))-1;
for k in divisors(N)[1:]:
    boz = n
    while (n % k == 0):
        n = n//k
    if (n % k == 1):
	    ans += 1
    n = boz
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

def divisior(n):
    a = []
    i = 1
    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i != n): a.append(n//i)
        i += 1

    return a

ans = 0
a = divisior(n).sort()

for x in a[1:]:
    tmp = n
    while (tmp%x == 0): tmp = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)

Submission status: Runtime Error

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

def FFF(i,K):
    if i==1:
        return True
    elif i<K:
        return False
    else:
        if i%K==0:
            return FFF(i//K,K)
        else:
            return FFF(i%K,K)

N=int(input())
lis=list(set(make_divisors(N)+make_divisors(N-1)))
ans=0
for i in lis[1:]:
    if FFF(N,i)==True:
        ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
def divisors(n):
  small = []
  large = []
  i = 1
  while i * i <= n:
    if not n % i:
      small.append(i)
      large.append(n // i)
    i += 1
  if small[-1] == large[-1]:
    large.pop()
  return small + large[::-1]

n = int(input())
res = set(divisors(n - 1))
res.remove(1)

for d in divisor(n):
  if d == 1:
    continue
  now = n
  # simulation
  while not now % d:
    now //= now
  if now % d == 1:
    res.add(d)

print(len(res))

Submission status: Runtime Error

Solution code:
n = input()


def is_k_ok(k, n):
    judge = False
    n_mod_k = n % k
    
    if n_mod_k == 1:
        return True
    
    elif n_mod_k == 0:
        while n % k == 0:
            n = n // k
            
        if n % k == 1:
            return True
        
    return judge 


print(len([k for k in range(2, n+1) if is_k_ok(k, n)]))

Submission status: Runtime Error

Solution code:
from math import gcd, sqrt
from collections import Counter

n = int(input()) 
times = 0

# 公約数を求める
def gcd(tmpn):
    lists = []
    while True:
        end = True
        for i in range(2, int(sqrt(tmpn)) + 1):
            if tmpn % i == 0:
                lists.append(i)
                tmpn = tmpn // i
                end = False         
        if end:  
            lists.append(tmpn)
            break
    return lists
    
def gori(lists, num=1, ans=[]):
    if len(lists) == 0:
        ans.append(num)
        return ans
    for i in range(len(lists)):
        tmp = lists[0:i] + lists[i + 1:len(lists)]
        ans = gori(tmp, num * lists[i], ans)
        ans = gori(tmp, num, ans)
    return ans

# 1を除いた公約数の個数を出力する
a = Counter(gcd(n - 1))
times = sum(map(lambda x: x+1, a.values())) - 1

a = set(gori(gcd(n)))
a.remove(1)

for i in a:
    tmp = n // i
    if tmp < i:
        if tmp == 1:
            times += 1
        
    else:
        while True:
            if tmp < i:
                if tmp == 1:
                    times += 1
                    break
            if tmp % i == 0:
                tmp = tmp // i
                    
            else:
                if tmp % i == 1:
                    times += 1
                break

print(times)

Submission status: Runtime Error

Solution code:
n = int(input())
z = range(2,n+1)
counter = 0

for i in z:
  while(n!=1):
		if n % i == 0:
  			n = n // i 
		else: 
  			n = n - i
    if n == 1:
      counter += 1
    else:
      break

Submission status: Runtime Error

Solution code:
n = int(input())
z = range(2,k+1)
counter = 0

for i in z:
  while(n!=1):
		if n % k == 0:
  			n = n // k 
		else: 
  			n = n - k
    if n == 1:
      counter += 1
    else:
      break

Submission status: Runtime Error

Solution code:
#関数f:入力xの1以外の約数をリストで出力
def f(x):
  out=set() #約数を保存するセット
  for i in range(1, (pow(x, 1/2)):
    #1-x**(1/2)未満の整数iについて、xを割り切れるか判定
    if x%i==0:
      #xをiで割り切れるのであれば、iとx/iを保存
      out.add(i)
      out.add(x//i)
      
  #x**(1/2)でxを割り切れる(つまりxが平方数)なら、出力にx**(1/2)を追加
  if x%(x**(1/2))==0:
    out.add(x**(1/2))
    
  #セットから昇順のリストに変換します
  out=list(out)
  out.sort()
  
  #昇順にした結果1が先頭に来ているため、インデックス1以降を出力
  return out[1:]

#入力受け取り
N=int(input())
ans=0 #最後に出力する変数

for K in f(N): #Nの1以外の約数について、操作の結果1になるかをそれぞれ調べる
    x=N #Nを直接書き換えると後に影響するため、ここではxとする
    #xをKで割り切れる間は、Kで割り続ける
    while x%K==0:
      x/=K
      
    #xをKで割り切れなくなったら、xからKを引けるだけ引く(=割って余りをとる)
    x%=K
    
    #操作後x=1となったならば、出力に1を足す
    if x==1:
        ans+=1
        
#(N-1)の1を除いた約数はすべて条件を満たすため、出力にf(N-1)の要素数を足す
ans+=len(f(N-1))

#出力
print(ans)

Submission status: Runtime Error

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    def divisors(x):
        r1 = deque()
        r2 = deque()
        for i in range(1,int(x**0.5)):
            if x % i == 0:
                r1.append(i)
                r2.appendleft(x//i)
        if int(x**0.5) == x**0.5:
            r1.append(int(x**0.5))
        return list(r1+r2)
    #N-1の約数
    ans = len(divisors(N-1))-1
    

    for d in divisors(N)[1:]:
        tmpN = N
        while tmpN % d == 0:
            tmpN //= d
        if tmpN % d == 1:
            ans += 1

            
            
    print(ans)


    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# 素因数分解

N=int(input())
cand=[]

def check(N0,K0):
    if N0%K0==0:
        return check(int(N0/K0),K0)
    elif N0%K0==1:
        return 1
    else:
        return 0

def check0(N0,K0):
    while N0%K0==0:
        N0=int(N0/K0)
    if N0%K0==1:
        return 1
    else:
        return 0

# N-1の約数の数
for i in range(2,int((N-1)**0.5)+1):#O(N**0.5)
    if (N-1)%i==0:
        cand.append(i)
        cand.append(int((N-1)/i))

# Nの約数
for i in range(2,int(N**0.5)+1):#O(N**0.5)
    if N%i==0:
        cand.append(i)
        cand.append(int(N/i))
cand.append(N)
cand.append(N-1)

count=0
for i in range(len(cand)):
    if check(N,cand[i]):
        count+=1

print(count)