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:
import math

a,b = map(int,input().split())
c = math.gcd(a,b)

ans = 0
i = 2
while c != 1:
    while c % i == 0:
        c = c // i
    #print(c,i,ans)
    i = i + 1
    ans += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
import math

a,b = map(int,input().split())
c = math.gcd(a,b)

ans = 0
i = 2
while c != 1:
    while c % i == 0:
        c = c // i
    print(c,i,ans)
    i = i + 1
    ans += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd
 
def primeNum(n):
  prime=[1]
  if n % 2 == 0:
    prime.append(2)
    while n % 2 == 0:
      n = n // 2
  for k in range(3, n+1, 2):
    if n % k == 0:
      prime.append(k)
      while n % k == 0:
        n = n // k
    if n == 1:
      return prime
 
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(len(primeNum(n)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math


def factorize(n: int):
    res = []
    for i in range(2, int(n ** 0.5//1 + 2)):
        if n % i:
            continue
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        res.append([i, s])
    return res


def solve(A: int, B: int):
    g = math.gcd(A, B)
    f = factorize(g)
    print(1 + len(f))


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math


def solve(A: int, B: int):
    g = math.gcd(A, B)
    f = factorize(g)
    print(1 + len(f))


def factorize(n: int):
    res = []
    for i in range(2, int(n ** 0.5//1 + 2)):
        if n % i:
            continue
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        res.append([i, s])
    return res


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math


def solve(A: int, B: int):
    # al = make_divisors(A)
    # bl = make_divisors(B)
    # l = sorted(al & bl)
    gcd = math.gcd(A, B)
    f = factorize(gcd)
    print(1 + len(f))


def factorize(n: int):
    res = []
    end = int(n ** 0.5//1 + 2)
    for i in range(2, end):
        if n % i:
            continue
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        res.append([i, s])
    return res


# 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


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

#define rep(i, a, n) for(int i = a; i < (n); ++i)
#define ll long long

template<typename T>
bool isPrime(T x) {
  if (x == 1) return false;
  for (int i = 2; i <= sqrt(x); i += 2) {
    if (x % i == 0) return false;
  }
  return true;
}

template<typename T>
T gcd(T n, T m) {
  while (m != 0) {
    n %= m;
    swap(n, m);
  }
  return n;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll a, b;
  cin >> a >> b;
  
  ll x = gcd(a, b);
  ll ans = 1;
  for (int i = 1; i * i <= x; ++i) {
    if (x % i == 0) {
      if (isPrime(i)) {
       ++ans;
       if (i * i != x) {
         if (isPrime(x / i)) ++ans;
       }
      }
    }
  }
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
def get_gcd(a, b):
  if b > a:
    a, b = b, a
    r = a%b
    if r == 0:
      return b
    else:
      return get_gcd(b, r)

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

A, B = map(int, input().split())
gcd = get_gcd(A, B)
factors = prime_factorize(gcd)
print(len(set(factors)))

Submission status: Runtime Error

Solution code:
A, B = map(int, input().split())
# https://www.iandprogram.net/entry/2015/03/18/003511
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(x, x%y)
# https://qiita.com/kageyasai2/items/48ef81f39b4e31c6d396
def factorize(n):
    factor = [1]
    for num in range(2, n*0.5+1):
        while n % num == 0:
            n //= num
            factor.append(num)
    return set(factor)
    
g = gcd(A, B)
f = factorize(g)
print(len(f))

Submission status: Runtime Error

Solution code:
from math import gcd as g
import math, copy
from sympy import primerange
a, b = map(int, input().split())
t = g(a,b)


def divisor(n): #1以外の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.remove(1)
    return table

if t ==1:
    print(1)
else:
    l = divisor(t)
    x = copy.deepcopy(l)

    for i in x:
        num = int(math.sqrt(i)) + 1
        primlist = list(primerange(2,num))

        for k in primlist:
            if i % k == 0:
                tem = i
                l.remove(tem)
                break
            
    else:
        print(len(l)+1)

Submission status: Runtime Error

Solution code:
import math as m

A, B = list(map(int, input().split()))
#A , B = 12, 18
def lcm(a, b):
    return (A * B) // m.gcd(A, B)

def sieve_of_eratosthenes(n): # n以下の素因数を求める
    candidate = [1 for i in range(n+1)]
    candidate[0:2] = [0 , 0]
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

def prime_factorize(A):
    p = sieve_of_eratosthenes(A)
    a = [0 for i in p]
    for i in range(len(p)):
        if A % p[i] != 0:
            a[i] = 0
        else:
            temp = A
            while temp % p[i] == 0:
                temp = temp / p[i]
                a[i] = a[i] + 1
    return a

pf = prime_factorize(m.gcd(A, B))
num = 1

for x in pf:
    if x >= 1:
        num = num + 1

print(num)

Submission status: Runtime Error

Solution code:
import math
import collections

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

n=list(map(int, input().split()))
a=math.gcd(n[0], n[1])
c = collections.Counter(prime_factorize(a))
b=list(c.keys())
d=len(b)
print(d+1)

Submission status: Runtime Error

Solution code:
import sympy
def euqlid(x,y):
    if x < y:
        tmp = x
        x  = y
        y = tmp
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
k = euqlid(a, b)
data = sympy.factorint(k)
print(len(data) + 1)

Submission status: Runtime Error

Solution code:
import sympy
def euqlid(x,y):
    if x < y:
        tmp = x
        x  = y
        y = tmp
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
k = euqlid(a, b)
data = sympy.factorint(k)
print(len(data) + 1)

Submission status: Runtime Error

Solution code:
#include"stdio.h"
#include"stdlib.h"
int gcd( int A, int B){
  if( A> B){
    return gcd( A-B, B);
  }
  else if( A< B){
    return gcd( A, B-A);
  }
  else{
    return A;
  }
}
int main(void){
  int A,B;
  scanf("%d %d",&A,&B);
  printf("%d\n",gcd( A, B));
  return 0;
}

Submission status: Runtime Error

Solution code:
 以下ペースト可
# start 21:14
a, b = [int(item) for item in input().split()]

if b > a:
    c = a
    a = b
    b = c


# 最大公約数を求める
def gcd(a, b):
    while b > 1:
        a, b = b, a%b
    return a

# 公約数でかつ素数の_listを求める
prime_devisor_list = [1]

import math

def is_prime(num):
    if num in [1, 2]:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

for i in range(2, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        # i can be ans
        # check pirme

        if is_prime(i):
            prime_devisor_list.append(i)

# 数をこたえる
print(len(prime_devisor_list))

Submission status: Runtime Error

Solution code:
 以下ペースト可
# start 21:14
a, b = [int(item) for item in input().split()]

if b > a:
    c = a
    a = b
    b = c


# 最大公約数を求める
def gcd(a, b):
    while b > 1:
        a, b = b, a%b
    return a

# 公約数でかつ素数の_listを求める
prime_devisor_list = [1]

import math

def is_prime(num):
    if num in [1, 2]:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

for i in range(3, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        # i can be ans
        # check pirme

        if is_prime(i):
            prime_devisor_list.append(i)

# 数をこたえる
print(len(prime_devisor_list))

Submission status: Runtime Error

Solution code:
# 
# VScodeで入力をテキストから読み込んで標準入力に渡す
import sys
import os
f=open(r'.\D\D_input.txt', 'r', encoding="utf-8")
# inputをフルパスで指定
# win10でファイルを作るとs-jisで保存されるため、読み込みをutf-8へエンコードする必要あり
# VScodeでinput file開くとutf8になってるんだけど中身は結局s-jisになっているらしい
sys.stdin=f

#
# 入力スニペット
# num = int(input())
# num_list = [int(item) for item in input().split()]
# num_list = [input() for _ in range(3)]
##################################
# 
# 以下ペースト可
# start 21:14
a, b = [int(item) for item in input().split()]

if b > a:
    c = a
    a = b
    b = c


# 最大公約数を求める
def gcd(a, b):
    while b > 1:
        a, b = b, a%b
    return a

# 公約数でかつ素数の_listを求める
prime_devisor_list = [1, 2]

import math

def is_prime(num):
    if num in [1, 2]:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

for i in range(3, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        # i can be ans
        # check pirme

        if is_prime(i):
            prime_devisor_list.append(i)

# 数をこたえる
len(prime_devisor_list)

Submission status: Runtime Error

Solution code:
from math import gcd as g
import math, copy
from sympy import primerange
a, b = map(int, input().split())
t = g(a,b)


def divisor(n): #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))
    return table

if t ==1:
    print(1)
else:
    l = divisor(t)
    x = copy.deepcopy(l)

    for i in x:
        num = int(math.sqrt(i)) + 1
        primlist = list(primerange(2,num))

        for k in primlist:
            if i % k == 0:
                tem = i
                l.remove(tem)
                break
            
    else:
        print(len(l))

Submission status: Runtime Error

Solution code:
import math
import fractions
def isprime(number):
    for i in range(2, round(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

A, B = map(int, input().split())
count = 1
N = fractions.gcd(A, B)

for i in range(2, N + 1):
  	if i != 2 and i % 2 == 0:
    	continue
    if N % i == 0:
        if isprime(i):
            count += 1

print(str(count))

Submission status: Runtime Error

Solution code:
import math
import fractions
def isprime(number):
    for i in range(2, round(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

A, B = map(int, input().split())
count = 1
N = fractions.gcd(A, B)

for i in range(2, N + 1):
  	if i != 2 and i % 2 == 0:
        continue
    if N % i == 0:
        if isprime(i):
            count += 1

print(str(count))

Submission status: Runtime Error

Solution code:
import math
import fractions
def isprime(number):
    for i in range(2, round(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

A, B = map(int, input().split())
count = 1
N = fractions.gcd(A, B)

for i in range(2, N + 1):
  	if i != 2 and i % 2 == 0:
      continue
    if N % i == 0:
        if isprime(i):
            count += 1

print(str(count))

Submission status: Runtime Error

Solution code:
import math

def isprime(number):
    for i in range(2, round(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

A, B = map(int, input().split())
count = 1
N = math.gcd(A, B)

for i in range(2, N + 1):
    if N % i == 0:
        if isprime(i):
            count += 1

print(str(count))

Submission status: Runtime Error

Solution code:
import math

def isprime(number):
    for i in range(2, round(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

A, B = map(int, input().split())
count = 1
N = math.gcd(A, B)

for i in range(2, N + 1):
    if N % i == 0:
        if isprime(i):
            count += 1
print(str(count))

Submission status: Runtime Error

Solution code:
import math

def isprime(number):
    for i in range(2, round(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

A, B = map(int, input().split())
count = 1
N = math.gcd(A, B)

for i in range(2, N + 1):
    if N % i == 0:
        if isprime(i):
            count += 1
            print(str(i))
print(str(count))

Submission status: Runtime Error

Solution code:
import math

def isprime(number):
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

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

if B < A:
    C = B
    B = A
    A = C
# A <= B

for i in range(2, round(A / 2 + 1):
    if A % i == 0:
        if B % i == 0:
            if isprime(i):
                count += 1

print(str(count))

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
def kannsuu(a,b):
    
    h = [i for i in range(1,max(a, b))if a % i == 0 and b % i == 0]
    import itertools
    import math
    y = 2
    kotae = []

    if len(h) ==[1] or h ==[1]:
        return(1)
    else:
        while y <= len(h):
            ln2 = list(itertools.combinations(h, y))
            kotae.extend(ln2)
            for q in range(0, len(ln2)):
                ln3 = list(itertools.combinations(ln2[q],2))
                for p in range(0, len(ln3)):
                    if math.gcd(ln3[p][0], ln3[p][1]) != 1:
                        if ln2[q] in kotae:
                            kotae.remove(ln2[q])                
                p = p + 1
            y = y + 1
        t = max(len(v) for v in(kotae))
        return(t)
x = kannsuu(a,b)
print(x)

Submission status: Runtime Error

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

c=fractions.gcd(A,B)

Cnt=[]

def prime_decomposition(n):
  i = 2
  table = set([])
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.add(int(i))
    i += 1
  if n > 1:
    table.add(int(n))
  return table

Cnt=prime_decomposition(c)

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

ans=1


for i in range(0,len(Cnt)):
    if is_prime(int(Cnt[i])):
        ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
ans = []

for i in range(1,min(a,b)+1):
    if a%i == 0 and b%i ==0:
        while True:
            for j in range(2,int(math.sqrt(i))+1):
                if i%j==0:
                    break
            else:
                ans.append(i)
            break
            
print(len(ans))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    # go = g
    # myset = set([1])
    sq = int(sqrt(g)) + 1
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit += 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

    print(-1) if dp[-1][-1] == inf else print(dp[-1][-1])

    return

# F


def F():
    S = input()
    print(solution(S))

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    import math

    vowels = "AIUEO"
    count = 0
    consonants = 0
    newC = []
    newV = []

    for i in S[:-1]:
        if i in vowels:
            count += 1
            newV.append(i)
        else:
            consonants += 1
            newC.append(i)

    if consonants < count or consonants - 2 > count:
        return 0

    a = math.factorial(len(set(newC))) * math.factorial(len(set(newV)))
    return a

    pass


# Solve
if __name__ == '__main__':
    E()

Submission status: Runtime Error

Solution code:
mport numpy as np
A, B = map(int, input().split())
while A%B > 0:
    c = A
    A = B
    B = c%B
P = [1]
if B%2 == 0:
    P.append(2)
for i in range(3, B//2 + 1, 2):
    if B%i == 0:
        P.append(i)
if B > 2:
    P.append(B)
    
l = len(P)
for i in range(2, l):
    if P[i] == 0:
        continue
    for j in range(i + 1, l):
        if P[j]%P[i] == 0:
            P[j] = 0
P = np.array(P)
print(np.where(P != 0)[0].size)

Submission status: Runtime Error

Solution code:
#%%
a = input()
#b = input()

A = [int(x) for x in a.split()]

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

gcb = math.gcd(A[0], A[1])  # 最大公約数

#%%
def prime_factorize(n):
    a = [1]
    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

so_gcb = prime_factorize(gcb)


#%%
new_num = []
for num in so_gcb:
    if num not in new_num:
        new_num.append(num)

print(len(new_num))

Submission status: Runtime Error

Solution code:
#%%
a = input()
#b = input()

#%%
#a = "12 18"
#b = "2 3 1"
#%%
A = [int(x) for x in a.split()]

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

gcb = math.gcd(A[0], A[1])  # 最大公約数

#%%
def prime_factorize(n):
    a = [1]
    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

so_gcb = prime_factorize(gcb)


#%%
new_num = []
for num in so_gcb:
    if num not in new_num:
        new_num.append(num)

print(len(new_num))

Submission status: Runtime Error

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

A,B = map(int,input().split())
GCD = math.gcd(A,B)
pf = prime_factorize(GCD)
print(len(set(pf))+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
input = sys.stdin.readline


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 set(divisors)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    a, b = map(int, input().split())

    divisors = []
    max_divisor = math.gcd(a, b)

    divisors = make_divisors(max_divisor)
    _, table = sieve(max(divisors))
    result = divisors & set(table)

    size = len(result) + 1
    print(size)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import itertools
import numpy as np
import sys
input = sys.stdin.readline


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 set(divisors)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    a, b = map(int, input().split())

    divisors = []
    max_divisor = math.gcd(a, b)

    divisors = make_divisors(max_divisor)

    _, table = sieve(max(divisors))

    result = divisors & set(table)

    # print(divisors)
    # print(result)

    size = len(result) + 1
    print(size)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import itertools
import numpy as np
import sys
input = sys.stdin.readline


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 set(divisors)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    a, b = map(int, input().split())

    divisors = []
    max_divisor = math.gcd(a, b)

    divisors = make_divisors(max_divisor)

    _, table = sieve(max(divisors))

    result = divisors & set(table)

    print(divisors)
    print(result)

    size = len(result) + 1
    print(size)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math,fractions
A,B = map(int,input().split())
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

GCD = fractions.gcd(A,B)
 
prime_list = get_sieve_of_eratosthenes(GCD)
counter = 1
for p in prime_list:
    if GCD % p == 0:
        counter += 1
        while(GCD % p == 0):
            GCD = GCD // p
        
print(counter)

Submission status: Runtime Error

Solution code:
import math
A,B = map(int,input().split())
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

GCD = math.gcd(A,B)
 
prime_list = get_sieve_of_eratosthenes(GCD)
counter = 1
for p in prime_list:
    if GCD % p == 0:
        counter += 1
        while(GCD % p == 0):
            GCD = GCD // p
        
print(counter)

Submission status: Runtime Error

Solution code:
import math
A,B = map(int,input().split())
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

GCD = math.gcd(A,B)

prime_list = get_sieve_of_eratosthenes(GCD)
counter = 1
for p in prime_list:
    if GCD % p == 0:
        counter += 1
        while(GCD % p == 0):
            GCD = GCD // p
        
print(counter)

Submission status: Runtime Error

Solution code:

import math
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

A,B = map(int,input().split())
d = max(A,B,A-B)

prime_list = get_sieve_of_eratosthenes(d)
ans = []
for p in prime_list:
    if A % p == 0 and B % p == 0:
        ans.append(p)
    while(A % p == 0):
        A = A // p
    while(B % p == 0):
        B = B // p
print(len(ans)+1)

Submission status: Runtime Error

Solution code:
import math

def sosus(N=0):
    count = 0
    soNum = {2}
    if N < 2:
        return {}
    for i in range(2,N+1):
        if judge_sosu(i) and N%i==0:
            soNum.add(i)
    return soNum

def sosu_num(N=0):
    return len(sosus(N))

def judge_sosu(N=0):
    for i in range(2,int(N**(1/2)+1)):
        if N % i == 0:
            return False
    return True

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

n = math.gcd(A,B)
#print(sosus(n))
print(sosu_num(n)+1)

Submission status: Runtime Error

Solution code:
gcd_memo = {}

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

def gcd(x, y):
    if x > y:
        x,y = y,x
    if (x,y) in gcd_memo:
        return (gcd_memo(x,y))
        
    z = y % x
    if z == 0:
        return x
        
    ret = gcd(x, z)
    gcd_memo[(x,y)] = ret
    return ret

my_gcd = gcd(A, B)

num_list = [i for i in range(3, my_gcd + 1, 2) if A % i ==0 and B % i == 0]
num_list.insert(0,1)
if A % 2 == 0 and B % 2 == 0:
    num_list.insert(1,2)

ans_list = []

i = 0
while i < len(num_list):
    j = i+1
    while j < len(num_list):
        if gcd(num_list[j], num_list[i]) != 1:
            num_list.pop(j)
            continue
        j += 1
    i += 1
print(len(num_list))

Submission status: Runtime Error

Solution code:
import math
a,b=[int(x) for x in input().split()]
i=1
g=math.gcd(a,b)
l=[]
while(i*i<=g):
    if g%i==0 and i*i!=g:
        l.append(i)
        l.append(g//i)
    if i*i==g:
        l.append(i)
    i=i+1
l=sorted(l)
i=1
while(i<len(l)):
    if l[i]!=0:
        j=i+1
        while(j<len(l)):
            if l[j]%l[i]==0:
                l[j] = 0
            j=j+1
    i=i+1
l=list(filter ( lambda x:x!=0,l))
print(len(l))

Submission status: Runtime Error

Solution code:
import math
a,b=[int(x) for x in input().split()]
i=1
g=math.gcd(a,b)
l=[]
while(i*i<=g):
    if g%i==0:
        l.append(i)
        l.append(g//i)
    i=i+1
l=sorted(l)
i=1
while(i<len(l)):
    if l[i]!=0:
        j=i+1
        while(j<len(l)):
            if l[j]%l[i]==0:
                l[j] = 0
            j=j+1
    i=i+1
l=list(filter ( lambda x:x!=0,l))
print(len(l))