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

Solution code:
#D
a,b=map(int,input().split())
#x>y
def gcd(x,y):
    if y==0:
        return x
    elif y==1:
        return 1
    else:
        return gcd(y,x%y)
c=gcd(a,b)
def f(n):
    s = []
    while n % 2 == 0:
        s.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            s.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        s.append(n)
    return s
d=f(c)
t=len(d)
count=0
if t!=0:
    count+=1
for i in range(t-1):
    if d[i]!=d[i+1]:
        count+=1
print(count+1)

Submission status: Accepted

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

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

    divisors.sort()
    return divisors

def main():
    A, B = [int(x) for x in input().split()]
    x = fractions.gcd(A, B)
    divisors = make_divisors(x)

    ans = 0
    for k in divisors:
        if k == 1:
            ans += 1
            continue

        factor = 0
        if k % 2 == 0 and k != 2:
            continue

        # 繰り返しの上限を対象の平方根にする
        for x in range(2, math.floor(math.sqrt(k)) + 1):
            if k % x == 0:
                factor += 1

        if factor == 0:
            ans += 1

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

def gojo(a, b):
  if a < b:
    return gojo(b, a)
  if a % b > 0:
    return gojo(b, a % b)
  else:
    return b

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())
c = collections.Counter(prime_factorize(gojo(a, b)))
print(len(c) + 1)

Submission status: Accepted

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


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


i_min = min(a, b)
i_max = max(a, b)

yaku_list = make_divisors(i_min)

kouyaku_list = []
for i in yaku_list:
    if i_max % i == 0:
        kouyaku_list.append(i)

for i in range(len(kouyaku_list) - 1):
    if kouyaku_list[i] == 1:
        continue
    if kouyaku_list[i] != -1:
        for j in range(i + 1, len(kouyaku_list)):
            if kouyaku_list[j] % kouyaku_list[i] == 0:
                kouyaku_list[j] = -1

print(len(kouyaku_list) - kouyaku_list.count(-1))

Submission status: Accepted

Solution code:
#a>b
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
#a>b
def lcm(a,b):
    return a*b // gcd(a,b)
def divisor(n):
    a = []
    root_n = int(n**0.5)
    for i in range(root_n):
        if n % (i+1) == 0:
            a.append(i+1)
            if (i+1) != n // (i+1):
                a.append(n//(i+1))
    a.sort()
    return a
A,B = map(int,input().split())
c = max(A,B)
d = min(A,B)
llcm = gcd(c,d)
yakus = divisor(llcm)

ans = 1
yak_flag = [1] * len(yakus)
for i in range(len(yakus)):
    if i == 0:
        continue
    k = yakus[i]
    if yak_flag[i] == 0:
        continue
    for j in range(i+1,len(yakus)):
        if yak_flag[j] == 0:
            continue
        if gcd(yakus[j],k) != 1:
            yak_flag[j] = 0
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
    
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct


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

g = gcd(A, B)

result_set = set(factorize(g))

print(len(result_set) + 1)

Submission status: Accepted

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

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
      if n % i == 0:
          divisors.append(i)
          if i != n // i:
              divisors.append(n//i)
  divisors.sort()
  return divisors
  
def f(list1, list2):
  output=[]
  a=0
  b=0
  len1=len(list1)
  len2=len(list2)
  
  while a<len1 and b<len2:
    if list1[a]<list2[b]:
      a+=1
    elif list1[a]>list2[b]:
      b+=1
    else:
      output.append(list1[a])
      a+=1
      b+=1
      
  return output

As=make_divisors(A)
Bs=make_divisors(B)

Cs=f(As, Bs)
lenc=len(Cs)
tag=[1]*lenc
for i in range(1, lenc):
  if tag[i]==1:
    for j in range(i+1, lenc):
      if Cs[j]%Cs[i]==0:
        tag[j]=0
        
print(sum(tag))

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
import collections
import fractions
a,b = map(int,input().split())
g = fractions.gcd(a,b)
c = collections.Counter(prime_factorize(g))
print(len(c)+1)

Submission status: Accepted

Solution code:
import math

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

def decompose(n):
	result = []
	
	i = 2
	n2 = math.floor(math.sqrt(n)) + 1
	while i <= n2:
		if n % i == 0:
			result.append(i)
			n //= i
			n2 = math.floor(math.sqrt(n)) + 1
		else:
			i += 1
	if n > 1:
		result.append(n)
	return result

def calc_gcm(a, b):
	if a > b:
		r = a % b
		a = r
	
	while a > 0:
		r = b % a
		b = a
		a = r
	
	return b

primes = decompose(calc_gcm(A, B))
count = 1
prev = 0
for p in primes:
	if prev != p:
		count += 1
	prev = p
print(count)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
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
if A != 1 and B != 1:
    AB = set(prime_factorize(A)) & set(prime_factorize(B))
    print(len(AB)+1)
else:
    print(1)

Submission status: Accepted

Solution code:
def gcd(n,m):
    while n:
        m,n = [n,m%n]
    return m

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

S = gcd(A,B)

s = 1
i = 2
while True:
    if S == 1:
        break
    if i ** 2 >= S:
        break
    hoge = 0
    while S % i == 0:
        hoge += 1
        S //= i
    if hoge:
        s += 1
    i += 1

print(s + (S != 1))

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
import fractions
readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True
a, b = readl()
mx = max(a,b)
t = make_divisors(min(a,b))
count = 0
for i in t:
    if mx % i == 0:
        if is_prime(i):
            count += 1
print(count)

Submission status: Accepted

Solution code:
# ABC141d
import sys
import heapq
import math
import fractions
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []


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


print(len(prime_decomposition(a).intersection(prime_decomposition(b)))+1)
exit()

for i in range(1, fractions.gcd(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))

Submission status: Accepted

Solution code:
def d_disjoint_set_of_common_divisors():
    A, B = [int(i) for i in input().split()]
    if A == 1 or B == 1:
        return 1

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数の辞書"""
        from collections import defaultdict
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return set(table.keys())
    a_primekey = prime_factorization_dict(A)
    b_primekey = prime_factorization_dict(B)
    ans = []
    for a in a_primekey:
        if a in b_primekey:
            ans.append(a)
    return len(ans) + 1

print(d_disjoint_set_of_common_divisors())

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
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 set(a)
f1 = prime_factorize(a)
f2 = prime_factorize(b)

print(len(f1.intersection(f1, f2)) + 1)

Submission status: Accepted

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

def gcd(a, b):
  while b != 0:
    a, b = b, a % b
  return(a)

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

div.sort()
ans = []
while len(div) != 0:
  d = div.pop(0)
  if d == 1:
    ans.append(d)
    continue
  div_c = div.copy()
  for i in range(len(div_c)):
    if div_c[i] % d == 0:
      div.remove(div_c[i])
  ans.append(d)

print(len(ans))

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
"""
互いに素な整数の組を選ぶ
A.Bの公約数は
12 18なら
1, 2, 3, 6
ってやっていくと無理がある
そもそも約数がある時点でだめでは？

"""

A, B = LI()
if A == B == 1:
    print(1)
    exit()
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    print(a)
    return a

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')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
A_fac = factorization(A)
B_fac = factorization(B)
perr(A_fac)
perr(B_fac)
ans = 1
b_fac = [b[0] for b in B_fac]
for a in A_fac:
    if a[0] in b_fac:
        ans += 1
#  for a, b in zip(A_fac, B_fac):
#      if a[0] == b[0]:
#          ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

def divisor(n: int) -> list:
    list_of_divisor = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            list_of_divisor.append(i)
            if i != n//i:
                list_of_divisor.append(n//i)
    list_of_divisor.sort()
    return list_of_divisor

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

g = gcd(a, b)
li = divisor(g)

cnt = 1
for i in li:
    if is_prime(i) == True:
        cnt += 1
    
print(cnt)

Submission status: Accepted

Solution code:
from fractions import gcd

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

ans = 1
n = d
for i in range(2, d + 1):
    if n % i == 0:
        ans += 1
        while n % i == 0:
            n //= i
    if n < i * i:
        if 1 < n:
            ans += 1
        break
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def prime_factors(n):
    ret = []
    apnd = ret.append
    while n >= 4:
        if n % 2:
            break
        else:
            n //= 2
            apnd(2)
    i = 3
    while n >= i * i:
        if n % i:
            i += 2
        else:
            n //= i
            apnd(i)
    apnd(n)
    return ret

def main():
    input = lambda: stdin.readline()[:-1]
    A, B = map(int, input().split())

    num = [1] + prime_factors(A) + prime_factors(B)
    num = set(num)
    ans = 0
    for i in num:
        if not A % i and not B % i:
            ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

[A,B] = list(map(int,input().split()))

Ad = prime_factor(A)
Bd = prime_factor(B)
ABd = set(Ad) & set(Bd)
print(len(ABd)+1)

Submission status: Accepted

Solution code:
import itertools

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

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

def main():
    A, B = map(int, input().split())

    div_A = divisor(A)
    div_B = divisor(B)
    C = list(set(div_A) & set(div_B))
    cnt = 1
    for c in C:
        if is_prime(c):
            cnt += 1

    print(cnt)

main()

Submission status: Accepted

Solution code:
#import sys

def gcd(a,b):
    if a>b :
        while b!=0:
            a,b = b,a%b
        return a
    else :
        while a!=0:
            a,b = b%a,a
        return b

def pff(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    return pf

A, B = map(int, input().split())
Scount = []
ans = int(0)
count= int(0)
a = int(0)
b = int(0)

a = gcd(A, B)

b = pff(a)

ans = len(b)+1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import fractions
A,B = [int(x) for x in stdin.readline().rstrip().split()]
GCD = fractions.gcd(A,B)
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = len(set(prime_factorize(GCD)))
print(ans+1)

Submission status: Accepted

Solution code:
import fractions

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


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)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return arr


f = fractions.gcd(a, b)

t = len(factorization(f))

if t == 1 and factorization(f)[0] == 1:
    print(t)
else:
    print(t + 1)

Submission status: Accepted

Solution code:
import math
import fractions
import sys
sys.setrecursionlimit(2000000000)
a,b= list(map(int, input().split()))
ma=fractions.gcd(a,b)
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 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
ans=1
for i in make_divisors(ma):
    if is_prime(i):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a % b)


@mt
def slv(A, B):
    ad = [v for v in divisor(A)]
    bd = [v for v in divisor(B)]
    cd = list(set(ad) & set(bd))
    cd.sort()
    ans = [1]
    for i in range(1, len(cd)):
        for j in range(1, i):
            if cd[i] % cd[j] == 0:
                break
        else:
            ans.append(cd[i])
    
    return len(ans)




def main():
    A, B = read_int_n()
    print(slv(A, B))

    # A = random.randint(10**11, 10**12)
    # B = random.randint(10**11, 10**12)
    # print(A, B)
    # print(slv(A, B))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math


def trial_division(n):
    # 素因数を格納するリスト
    factor = set()
    # 2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.add(num)
    # リストが空ならそれは素数
    if not factor:
        return set((1, n))
    else:
        factor.add(n)
        factor.add(1)
        return factor


A, B = map(int, input().split())
# print(trial_division(A))
# print(trial_division(B))
print(len(trial_division(A) & trial_division(B)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)


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

factorization(24)

def solve():
    A, B = LI()

    if A == 1 and B == 1:
        print(1)
        return

    a_primes = factorization(A)
    b_primes = factorization(B)

    dprint(a_primes)
    dprint(b_primes)

    print(len(set([x[0] for x in a_primes])&set([y[0] for y in b_primes]))+1)
solve()

Submission status: Accepted

Solution code:
def gcd(a : int, b: int):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

a, b = map(int, input().split())
g = gcd(a, b)
ans = set([1])
for i in range(2, 1000000):
    while g % i == 0:
        g = g // i
        ans.add(i)
if g > 1:
    ans.add(g)

print(len(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd

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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    A, B = map(int, input().split())
    C = gcd(A, B)
    l = factorization(C)
    if l == [[1, 1]]:
        print(1)
    else:
        ans = len(l) + 1
        print(ans)


if __name__ == '__main__': main()

Submission status: Accepted

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

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

hoge_a = set(prime_factorize(a))
hoge_b = set(prime_factorize(b))
ans = len(hoge_a & hoge_b) +1
print(ans)

Submission status: Accepted

Solution code:
import math
import heapq
from bisect import bisect_right, bisect_left
from collections import defaultdict, Counter
import itertools
import sys
from fractions import gcd
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")


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

    divisors.sort()
    return divisors


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


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



def main():
    a, b = map(int, input().split())
    l = make_divisors(a)
    d = Counter(l)
    ll = make_divisors(b)
    lll = []
    for i in range(len(ll)):
        if d[ll[i]] > 0:
            lll.append(ll[i])
    ans = 1
    for i in range(len(lll)):
        if is_prime(lll[i]):
            ans += 1
    print(ans)


    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
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 
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

  
n = gcd(A,B)
if(n == 1): ans = 1
else: ans = len(factorization(n))+1
print(ans)

Submission status: Accepted

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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    A,B=map(int,input().split())
    if A==1 and B==1:
        return 1
    AF=[x[0] for x in factorization(A)]
    BF=[x[0] for x in factorization(B)]
    return len(set(AF)&set(BF))+1
    

print(main())

Submission status: Accepted

Solution code:
a, b = list(map(int, input().split()))

# https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    if n == 1:
      return []
    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

import fractions

print(len(factorization(fractions.gcd(a, b)))+1)

Submission status: Accepted

Solution code:
import numpy as np
import fractions

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 = [int(e) for e in input().strip().split()]
g = fractions.gcd(a, b)
f = prime_factorize(g)
print(len(set(f)) + 1)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

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

f = factorization(gcd(a,b))
if f[0] != [1, 1]:
    f.append([1,1])
print(len(f))

Submission status: Accepted

Solution code:
import math
import fractions
from collections import Counter

def read():
    return int(input())

def readmap():
    return map(int, input().split())

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

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

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

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


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


if __name__ == "__main__":
    a, b = readmap()
    g = fractions.gcd(a, b)

    c = Counter(prime_factorize(g))

    print(len(c) + 1)

Submission status: Accepted

Solution code:
import math

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

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

common_divisors = make_divisors(a) & make_divisors(b)

ans = 1
for common_divisor in common_divisors:
    if is_prime(common_divisor):
        ans += 1

print(ans)

Submission status: Accepted

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

big=max(a,b)
sma=min(a,b)

while sma>0:
    mod=big%sma
    big=sma
    sma=mod

#print(big)

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

if big==1:
    print(1)
else:
    print(len(factorization(big))+1)

Submission status: Accepted

Solution code:
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

a,b = map(int, input().split())
x = set(factorize(a))
x = list(x)
y = set(factorize(b))
y = list(y)
z = x+y
z = [i for i in set(z) if z.count(i) > 1]
print(len(z)+1)

Submission status: Accepted

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

a,b = [list(map(int, s.split())) for s in open(0)][0]

al = set(prime_factorize(a))
bl = set(prime_factorize(b))
print(len(al & bl)+1)