Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    a,b = map(int,input().split())

    def make_two_divisors(a,b):
        lower_divisors,upper_divisors = [],[]
        prime_li = [True]*(max(a,b)+1)
        i = 1
        while i*i<=max(a,b):
            if prime_li[i]:
                if a%i==0 and b%i==0:
                    lower_divisors.append(i)
                    #if i != max(a,b)//i and a%(max(a,b)//i)==0 and b%(max(a,b)//i)==0:
                    #    upper_divisors.append(b//i)
                    if i!=1:
                        for j in range(i+i,max(a,b)+1,i):
                            prime_li[j]=False 
            i+=1
        return lower_divisors + upper_divisors[::-1]
    print(len(make_two_divisors(a,b)))

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

def get_primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

def factorization_num(n, pl):
    count = 0
    for p in pl:
        if n % p == 0: count += 1
    return count

A, B = map(int, input().split())
print(factorization_num(gcd(A, B), get_primes(gcd(A, B))) + 1)

Submission status: Runtime Error

Solution code:
from math import gcd

def get_primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

def factorization_num(n, pl):
    count = 0
    for p in pl:
        if n % p == 0: count += 1
    return count

A, B = map(int, input().split())
print(factorization_num(gcd(A, B), get_primes(gcd(A, B))) + 1)

Submission status: Runtime Error

Solution code:
import math

def get_primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

def factorization_num(n, pl):
    count = 0
    for p in pl:
        if n % p == 0: count += 1
    return count

A, B = map(int, input().split())
print(factorization_num(math.gcd(A, B), get_primes(math.gcd(A, B))) + 1)

Submission status: Runtime Error

Solution code:
import sympy as sym

a, b = map(int, input().split())
print(len(set(sym.primefactors(a)) & set(sym.primefactors(b))) + 1)

Submission status: Runtime Error

Solution code:

A, B = map(int, input().split())

divisor = []
for i in range(1, int(A ** 0.5) + 1):
    if A % i == 0:
        divisor.append(i)
        if i != A // i:
            divisor.append(A // i)

divisor = sorted(v for v in divisor if B % v == 0)
lim = divisor[-1]
ok = [True] * (lim + 1)
ans = 0
for v in divisor:
    if ok[v]:
        ans += 1
        ok[v] = False
        if v != 1:
            for i in range(2 * v, lim + 1, v):
                ok[i] = False

print(ans)

Submission status: Runtime Error

Solution code:
A, B = map(int,input().split())

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

lst_A = make_divisors(A)
lst_B = make_divisors(B)
cmn_lst = lst_A & lst_B
m = max(cmn_lst)

hurui = [1] * (m+1)
hurui[0] = 0
for j in range(2, m//2+1):
    for k in range(j, m+1, j):
        if k == j:
            continue
        hurui[k] += 1

cand = set()
for p, v in enumerate(hurui):
    if v == 1:
        cand.add(p)
print(len(cand & cmn_lst))

Submission status: Runtime Error

Solution code:
A, B = map(int,input().split())

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

lst_A = make_divisors(A)
lst_B = make_divisors(B)
cmn_lst = lst_A & lst_B
cmn = list(cmn_lst)
m = max(cmn)

hurui = [1] * (m+1)
hurui[0] = 0
for j in range(2, m//2+1):
    for k in range(j, m+1, j):
        if k == j:
            continue
        hurui[k] += 1

cand = set()
for i, v in enumerate(hurui):
    if v == 1:
        cand.add(i)
print(len(cand & cmn_lst))

Submission status: Runtime Error

Solution code:
A, B = map(int,input().split())

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

lst_A = make_divisors(A)
lst_B = make_divisors(B)
cmn_lst = lst_A & lst_B
m = max(cmn_lst)

hurui = [1] * (m+1)
hurui[0] = 0
for j in range(2, m//2+1):
    for k in range(j, m+1, j):
        if k == j:
            continue
        hurui[k] += 1

cand = set()
for i, v in enumerate(hurui):
    if v == 1:
        cand.add(i)
print(len(cand & cmn_lst))

Submission status: Runtime Error

Solution code:
A, B = map(int,input().split())

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

lst_A = make_divisors(A)
lst_B = make_divisors(B)
cmn_lst = lst_A & lst_B
m = max(cmn_lst)

hurui = [1] * (m+1)
hurui[0] = 0
for j in range(2, m//2+1):
    for k in range(j, m+1, j):
        if k == j:
            continue
        hurui[k] += 1

cand = set()
for i, v in enumerate(hurui):
    if v == 1:
        cand.add(i)
print(len(cand & cmn_lst))

Submission status: Runtime Error

Solution code:
A, B = map(int,input().split())

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

lst = make_divisors(A, B)
m = max(lst)

hurui = [1] * (m+1)
hurui[0] = 0
for j in range(2, m//2+1):
    for k in range(j, m+1, j):
        if k == j:
            continue
        hurui[k] += 1

cand = []
for i, v in enumerate(hurui):
    if v == 1:
        cand.append(i)
print(len(set(cand) & set(lst)))

Submission status: Runtime Error

Solution code:
import math

d=math.gcd(a,b)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
r=make_divisors(d)
l=len(r)
ans=1
w=[True]*l
if l>=2:
  for x in range(1,l):
    if w[x]==True:
      ans+=1
      for y in range(x,l):
        if r[y]%r[x]==0:
          w[y]=False
          
print(ans)

Submission status: Runtime Error

Solution code:
def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f +=6
    return True  

def resolve():
    A, B = list(map(int, input().split()))
    import sympy
    divs = sympy.divisors(A)
    i = 1
    cnt = 0
    while i < len(divs):
        if B%divs[i]==0 and is_prime(divs[i]):
            cnt += 1
        i += 1
    print(cnt+1)
    

if '__main__' == __name__:
    resolve()

Submission status: Runtime Error

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

A,B = (int(x) for x in input().rstrip('\n').split())
c = math.gcd(A,B)
if c==1:
  print(1)
else:
  res = 1
  d = math.floor(math.sqrt(c))
  for i in range(2,d+2):
    if c%i==0:
      res += 1
      while c%i==0:
        c = c//i
  if res == 1:
    res += 1
print(res)

Submission status: Runtime Error

Solution code:
from math import gcd
n,m=map(int,input().split())
gcd=gcd(m,n)
memory=[0]*(gcd)
count=0
for i in range(2,gcd+1):
    if memory[i-1]==0 and gcd%i==0:
        count+=1
        k=1
        while True:
            memory[k*(i)-1]+=1
            k+=1
            if k*i-1>gcd-1:
                break
print(count+1)

Submission status: Runtime Error

Solution code:
import numpy as np

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

  
a, b = map(int,input().split())
ad = make_divisors(a)
bd = make_divisors(b)
ab = list(set(ad) & set(bd))
ab.sort()
# print(ab)

prime = [1]
is_p = np.array([True]*(ab[-1]+1))
is_p[0] = False
for i in range(2, ab[-1]+1):
    if is_p[i]:
        prime.append(i)
        is_p[i::i] = False
# print(prime)

ans = list(set(ab) & set(prime))
print(len(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys

input = sys.stdin.buffer.readline

A,B = map(int,input().split())

divA,divB = set(),set()
for i in range(1,int(A**.5+1)):
    if A%i == 0:
        divA.add(i)
        divA.add(A//i)
for i in range(1,int(B**.5+1)):
    if B%i == 0:
        divB.add(i)
        divB.add(B//i)

C = list(divA & divB)
C.sort()

N = 10**6+1
primes = []
is_prime = [True]*N
for i in range(2,N):
    if is_prime[i]:
        primes.append(i)
        j = 2
        while i*j < N:
            is_prime[i*j] = False
            j += 1

ans = 0
for c in C:
    if is_prime[c]:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
A,B = map(int,input().split())
from fractions import gcd
C = gcd(A,B)
num = []
for i in range(2,int(C**0.5)+1):
    while C%i==0:
        num.append(i)
        C //= i
if C != 1:
    num.append(C)
    from collections import Counter
CC = Counter(num)
print(len(CC)+1)

Submission status: Runtime Error

Solution code:
import math

def gcd(a, b):
    big = max(a, b)
    small = min(a, b)
    r = small
    while r != 0:
        r = big % small
        big = small
        small = r
    
    return big
    
def divisor(n):
    lower = []
    upper = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            lower.append(i)
            
            if i * i != n:
                upper.append(n // i)
    
    return lower + upper[::-1]

def common_divisor(a, b):
    big = max(a, b)
    small = min(a, b)
    
    div_s = divisor(small)
    
    div = []
    for s in div_s:
        if big % s == 0:
            div.append(s)
    
    return div
    
    
def main():
    a, b = map(int, input().split())
    g = gcd(a, b)
    
    prime_number = [True] * (g + 1)
    
    for i in range(2, g + 1):
        for j in range(2, g + 1):
            if not prime_number[i]:
                continue
        
            if g < i * j:
                continue

            prime_number[i * j] = False
     
    c_div = common_divisor(a, b)       
    ans = 0
    
    for c in c_div:
        if prime_number[c]:
            ans += 1
    
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    from collections import deque
    divisors = deque([])
    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)
    lst_divisors = list(divisors)
    lst_divisors.sort()
    return lst_divisors

a, b = map(int,input().split())

ya = set(make_divisors(a))
yb = set(make_divisors(b))

cand = list(ya&yb)
cand.sort()

#print(cand)

num = [0]*(cand[-1]+1)

ans = 0
for n in cand[1:]:
    if n > cand[-1]:
        break
    if num[n]:
        continue
    num[2*n::n] = list(map(lambda x:1,num[2*n::n]))
    ans += 1
    #print(n)

print(ans+1)#1の分

Submission status: Runtime Error

Solution code:
import numpy as np

def make_divisors(n):
    from collections import deque
    divisors = deque([])
    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)
    lst_divisors = list(divisors)
    lst_divisors.sort()
    return lst_divisors

a, b = map(int,input().split())

ya = set(make_divisors(a))
yb = set(make_divisors(b))

cand = list(ya&yb)
cand.sort()

#print(cand)

num = np.array([0]*(cand[-1]+1))

ans = 0
for n in cand[1:]:
    if num[n]:
        continue
    #print(n)
    ans += 1
    num[2*n::n] = 1
#print(num)
print(ans+1)#1の分

Submission status: Runtime Error

Solution code:
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    table = sorted(table)
    return table

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

A_list = set(divisor(A))
B_list = set(divisor(B))

list = A_list & B_list

cnt = 1

for i in list:
    if is_prime(i):
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
from math import gcd

A, B = map(int, input().split())

D = gcd(A, B)
d = D.copy()
ans = 1
i = 2
while i <= pow(D, 1/2):
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        lower, upper = [], []
        i = 1
        while i * i <= n:
            if n % i == 0:
                lower.append(i)
                if i != n // i:
                    upper.append(n // i)
            i += 1
        return lower + upper[::-1]

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    A, B = Scanner.map_int()
    div_A = Math.divisor(A)
    div_B = Math.divisor(B)
    X = set(div_A) & set(div_B)
    ans = 0
    for x in X:
        if Math.is_prime(x):
            ans += 1
    print(ans + 1)


def main():
    # sys.setrecursionlimit(1000000)
    sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def sieve(n, a, b):
    ans = 0
    can_divide = [False] * (n + 1)
    can_divide[0] = False
    can_divide[1] = True
    ans += 1
    for i in range(2, int(n ** 0.5) + 1):
        if can_divide[i] is False and a % i == 0 and b % i == 0:
            ans += 1
            for j in range(i * 2, n + 1, i):
                can_divide[j] = True

    return ans


a, b = map(int, input().split())

m = min(a, b)

ans = sieve(m, a, b)

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a,b): #最大公約数
    if a%b==0: return b
    return gcd(b,a%b)

def ela(g):
    s={}
    i=2
    while i*i<=g:
        while g%i==0:
            g//=i
            s.add(i)
        i+=1
    return s

a,b=map(int,input().split())
G=gcd(max(a,b),min(a,b))
print(len(ela(G))+1)

Submission status: Runtime Error

Solution code:
from math import gcd

a, b = map(int, input().split())
data = []
for i in range(1, int(min(a, b) ** 0.5) + 1):
    if a % i == 0 and b % i == 0:
        data.append(i)
        if b % (a // i) == 0:
            data.append(a // i)
        if a % (b // i) == 0:
            data.append(b // i)
data = list(set(data)).sort()
for i in range(len(data)):
    j = i + 1
    while j < len(data):
        if gcd(data[i], data[j]) != 1:
            del data[j]
        else:
            j += 1
print(len(data))

Submission status: Runtime Error

Solution code:
#4問目
import math
import collections
A, B = map(int, input().split())

count = 0
gcd = fractions.gcd(A,B)

def devisor(num):
    array = []
    for i in range(1, math.floor(math.sqrt(num)) + 1):
        if(num % i == 0):
            array.append(i)
            array.append(math.floor(num / i))
    return array

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

print(len(collections.Counter(prime(gcd))) + 1)

Submission status: Runtime Error

Solution code:
#4問目
import math
A, B = map(int, input().split())

count = 0
gcd = math.gcd(A,B)

def devisor(num):
    array = []
    for i in range(1, math.floor(math.sqrt(num)) + 1):
        if(num % i == 0):
            array.append(i)
            array.append(math.floor(num / i))
    return array

def isPrime(n):
    if n <= 2:
        return True
    for p in range(2, n):
        if n % p == 0:
            return False
    return True

dev = devisor(gcd)
for i in dev:
    if isPrime(i):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

a, b = map(int, input().split())

class Mint(object):
    """ 整数のお役立ち計算
    - 繰り返し二乗法で効率的にn**kを求める（必要であればmodを指定）
    - 素数判定
    - 素因数分解
    - 約数列挙
    - nCrの計算(ピンポイントで求める or あるnまでのnCrを計算するのに必要な情報を一気に求める）
    - ToDo:
    # divisor : 配列をsortしているため遅い可能性あり
    """

    def gcd(self, a, b):
        # ユークリッドの互除法を用いる
        while b:
            a, b = b, a % b
        return a

    def lcm(self, a, b):
        return a * b // self.gcd(a, b)

    @staticmethod
    def cmb_(n, r):
        """ 普通にnCrを求める
        >>> p = Mint()
        >>> p.cmb_(10, 2)
        45
        """
        from operator import mul
        from functools import reduce

        r = min(n - r, r)
        if r == 0:
            return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1, r + 1))
        return over // under

    def cmb(self, n, r, mod: int = 10 ** 9 + 7):
        """ 事前にあるnまでの範囲で、nCrを高速に計算する
        >>> p = Mint()
        >>> p.cmb_prep(10)
        >>> p.cmb(10, 2)
        45
        """
        if (r < 0) or (r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % mod

    def cmb_prep(self, N: int, mod: int = 10 ** 9 + 7):
        self.g1 = [1, 1]  # 元テーブル
        self.g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

        for i in range(2, N + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    @staticmethod
    def iterated_power(z: int, n: int, mod=None) -> int:
        """ 繰り返し二乗法でn**kを求める（再帰処理は使わない）
        >>> p = Mint()
        >>> p.iterated_power(3, 10)
        59049
        >>> p.iterated_power(3, 10, 10)
        9
        """
        beta = bin(n)[2:]

        Z, q, t = z, 0, len(beta)
        while beta[t - q - 1] == '0':
            Z = Z * Z
            if mod is not None:
                Z = Z % mod
            q += 1
        result = Z

        for k in range(q + 1, t):
            Z = Z * Z
            if mod is not None:
                Z = Z % mod
            if beta[t - k - 1] == '1':
                result = result * Z
                if mod is not None:
                    result = result % mod

        if mod is not None:
            result = result % mod

        return result

    @staticmethod
    def factorization(n: int) -> dict:
        from collections import defaultdict

        arr = defaultdict(int)
        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[i] = cnt

        if temp != 1:
            arr[temp] = 1

        if arr == []:
            arr[n] = 1

        return arr

    @staticmethod
    def enumerate_prime(n: int) -> (list, dict, list):
        """
        n以下の素数を列挙する
        何で割るかを記録しておくことで、素因数分解が高速にできる
        >>> p = Mint()
        >>> p.enumerate_prime(11)
        ([2, 3, 5, 7, 11], {2: 0, 3: 1, 5: 2, 7: 3, 11: 4}, [0, 1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11])
        """

        lis_prime = [True] * (n+1)
        lis_prime[0] = False
        lis_prime[1] = False

        primes = []
        div_prime = [i for i in range(n + 1)]
        primes_idx = {}

        cnt = 0
        for i in range(2, n+1):
            if lis_prime[i]:
                primes.append(i)
                primes_idx[i] = cnt
                cnt += 1

                j = 2 * i
                while True:
                    if j > n:
                        break
                    lis_prime[j] = False
                    div_prime[j] = i
                    j += i

        return primes, primes_idx, div_prime

    @staticmethod
    def is_prime(n: int) -> bool:
        """
        素数判定
        >>> p = Mint()
        >>> p.is_prime(2)
        True
        >>> p.is_prime(43)
        True
        >>> p.is_prime(4)
        False
        """

        if n == 1:
            return False
        if n == 2:
            return True

        for i in range(2, n):
            if n % i == 0:
                return False
            if i * i > n:
                return True

    @staticmethod
    def divisor(n: int) -> list:
        """
        約数列挙
        >>> p = Mint()
        >>> p.divisor(6)
        [1, 2, 3, 6]
        """
        res = []
        if n == 1:
            return [1]

        for i in range(1, n):
            if n % i == 0:
                res.append(i)
                if i != n / i:
                    res.append(int(n / i))
            if (i+1) * (i+1) > n:
                res.sort()
                return res

mint = Mint()
c = mint.gcd(a, b)
# print(c)
candidates = mint.divisor(c)

primes, _, _ = mint.enumerate_prime(c)
# print(primes)

print(len(set(candidates) & set(primes))+1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

dp = [[10**10 for _ in range(2**n)] for j in range(m)]
dp[0][0] = 0
a, b = map(int, input().split())
c = list(map(int, input().split()))
idx = 0
for cc in c:
  idx += 2**(cc-1)
for j in range(1, 2**n):
  if ~idx & j == 0:
    dp[0][j] = a

for i in range(1, m):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  idx = 0
  for cc in c:
    idx += 2**(cc-1)
  for j in range(2**n):
    dp[i][j] = min(dp[i-1][j], dp[i-1][(j|idx)^idx]+a)

if dp[-1][-1] != 10**10:
  print(dp[-1][-1])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import math
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
sqrt = math.floor(g ** 0.5)
factors = [1]
z = g
for i in range(2, sqrt + 1):
    if not z % i:
        factors.append(i)
        while z % i == 0:
            z //= i
if z > 1:
    factors.append(i)
print(len(factors))

Submission status: Runtime Error

Solution code:
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


A, B = map(int, input().split())
divisor_list = cf(A,B)
if not divisor_list:
  print(1)
  else:
    prime_list = get_sieve_of_eratosthenes(max(divisor_list))
    print(sum([1 for i in divisor_list if i in prime_list])+1)

Submission status: Runtime Error

Solution code:
from fractions import gcd

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

a, b = map(int, input().split())
c = gcd(a, b)
count = 1
for num in primes(c):
  if c % num == 0:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
import math
a, b = map(int,input().split())
g = math.gcd(a,b)
p = []
d = []
for i in range(2,g):
    if g % i == 0:
        d.append(i)
for i in d:
    for j in p:
        if i % j == 0:
            break
    else:
        p.append(i)
ans = len(p) +1
print(ans)

Submission status: Runtime Error

Solution code:
import math
a, b = map(int,input().split())
g = math.gcd(a,b)
p = []
d = []
for i in range(2,g):
    if g % i == 0:
        d.append(i)
print(d)
for i in d:
    for j in p:
        if i % j == 0:
            break
    else:
        p.append(i)
ans = len(p) +1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations
A,B = map(int,input().split())

divisors = []
n,m = min(A,B), max(A,B)
for i in range(1,int(n**0.5)+1):
  if n%i==0 and m%i==0:
    divisors.append(i)
    p = n//i
    if m%p==0:
      divisors.append(p)

d = max(divisors)
isPrime = [True] * (d+1)
isPrime[0],isPrime[1] = False,False
for i in range(2, int(d ** 0.5) + 1):
  if isPrime[i]:
    for j in range(i * i, d + 1, i):
      isPrime[j] = False

ans = 1
for d in divisors:
  if isPrime[d]:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    import math
    return math.gcd(a, b)


def pf(v):
    s, e = 3, v
    result = 2 if v & 1 == 0 else 1
    while v & 1 == 0:
        v >>= 1
    for i in range(s, e, 2):
        if v == 1:
            break
        if v % i == 0:
            result += 1
        while v > 1 and v % i == 0:
            v //= i
    return result


a, b = list(map(int, input().split()))
print(pf(gcd(a, b)))

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
from math import *
c=gcd(a,b)
d=0
for i in range(1,c+1):
    if c%i==0:
        c//=i
        d+=+1
print(d)

Submission status: Runtime Error

Solution code:
A, B = [int(s) for s in input().split(' ')]
limit = min(A, B) // 2
p = [1] * (limit + 1)
p[0] = 0
p[1] = 0
d = dict()
d[1] = 1 
primes = []
for i in range(2, limit + 1):
    if p[i] == 1:
        # prime
        count = 0
        j = i + i
        while A % i == 0 and B % i == 0:
            count += 1
            A //= i
            B //= i
            p[j] = 0
            j += i
        if count > 0:
            d[i] = count
        if A == 1 or B == 1:
            break
    else:
        continue

print(len(d.keys()))

Submission status: Runtime Error

Solution code:
A, B = [int(s) for s in input().split(' ')]
limit = min(A, B)
p = [1] * (limit + 1)
p[0] = 0
p[1] = 0
primes = []
for i in range(2, limit + 1):
    if p[i] == 1:
        # prime
        primes.append(i)
        j = i + i
        while limit >= j:
            p[j] = 0
            j += i
    else:
        continue
d = dict()
d[1] = 1 
for pp in primes:
    count = 0
    while A % pp == 0 and B % pp == 0:
        count += 1
        A //= pp
        B //= pp
    if count > 0:
        d[pp] = count
print(len(d.keys()))

Submission status: Runtime Error

Solution code:
A, B = [int(s) for s in input().split(' ')]
limit = min(A, B)
p = [1] * (limit + 1)
p[0] = 0
p[1] = 0
primes = []
for i in range(2, limit + 1):
    if p[i] == 1:
        # prime
        primes.append(i)
        j = i + i
        while limit >= j:
            p[j] = 0
            j += i
    else:
        continue
d = dict() 
for pp in primes:
    count = 0
    while A % pp == 0 and B % pp == 0:
        count += 1
        A //= pp
        B //= pp
    if count > 0:
        d[pp] = count
print(1 + len(d.keys()))