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:
import math
def g(a, b):
    if b == 0:
        return a
    else:
        if a < b:
            a, b = b, a
        return g(b, a % b)


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

t = g(A, B)

k = 2
cnt = 0
while t > 1:
    limit = int(math.sqrt(t))
    if k > limit + 1:
        break
    if t % k == 0:
        cnt += 1
        while t % k == 0:
            t //= k
    k += 1
if not t == 1:
    cnt += 1
print(cnt + 1)

Submission status: Accepted

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

length = int(A ** 0.5) + 2
Ax = A
s = [1] * length
ans, i, lim, t = 1, 2, A ** 0.5, set()
while i < lim:
    if s[i] == 1:
        for j in range(i*2, length, i):
            s[j] = 0
        if A % i == 0:
            if B % i == 0:
                ans += 1
            while Ax % i == 0:
                Ax //= i
    i += 1

if Ax >= length and B % Ax == 0:
    ans += 1
print(ans)

Submission status: Accepted

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

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

X = 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)

    divisors.sort()
    return divisors

temp = make_divisors(X)
ans = []
ans.append(temp[0])
if len(temp) >= 2:
    ans.append(temp[1])

for i in range(2, len(temp)):
    for a in ans:
        if gcd(temp[i], a) != 1:
            break
    else:
        ans.append(temp[i])

print(len(ans))

Submission status: Accepted

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

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

a = factorization(A)
b = factorization(B)

ans = 1+len(list(set(a[:,0])&set(b[:,0])))
if A==B and A==1:
  ans=1
print(ans)

Submission status: Accepted

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

aa = make_divisors(a)
bb = make_divisors(b)

aaa = list(set(aa) & set(bb))

al = len(aaa)
count = 0



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


for i in range(al):
  if is_prime(aaa[i]):
    count += 1

print(count+1)

Submission status: Accepted

Solution code:
import math
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

a,b = IL()
num = int(math.sqrt(max(a,b)))
Ayakusuu = []
Byakusuu = []
ansl = []
ans = 0

numA = int(math.sqrt(a))
for i in range(1,numA+1):
  if a%i == 0:
    Ayakusuu.append(i)
    Ayakusuu.append(a//i)
#print(Ayakusuu)

numB = int(math.sqrt(b))
for i in range(1,numB+1):
  if b%i == 0:
    Byakusuu.append(i)
    Byakusuu.append(b//i)
#print(Byakusuu)
yakusuu = set(Ayakusuu) & set(Byakusuu)
#print(yakusuu)
for i in yakusuu:
  num2 = int(math.sqrt(i))
  for k in range(2,num2+1):
    if i%k == 0:
      break
  else:
    ansl.append(i)

for i in range(len(ansl)):
  for j in range(len(ansl)):
    if i == j:
      continue
    else:
      aa, bb = ansl[i], ansl[j]
      if aa == 1:
        continue
      else:
        num3 = min(aa,bb)
        for k in range(2,num3+1):
          if aa%k == 0 and bb%k == 0:
            break
        else:
          continue
        break
  else:
    ans += 1

#print(yakusuu)
#print(ansl)
print(ans)


"""
for i in itertools.combinations(ansl, 2):
  print(i)
  aa, bb = i
  if aa == 1:
    ans += 1
  else:
    num3 = min(aa,bb)
    for k in range(2,num3+1):
      if aa%k == 0 and bb%k == 0:
        break
    else:
      ans += 1

#print(yakusuu)
print(ansl)
print(ans)
"""

Submission status: Accepted

Solution code:
#import numpy as np
#from math 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

    
##################################################################

if __name__ == "__main__":
    Input1 = [input() for i in range(1)]
    #N = int(Input1[0])
    A,B = list(map(int,Input1[0].split()))
    if B > A:
        temp = A
        A = B
        B = temp

    ans = 1
    if B == 1:
        print(ans)
    else:
        fact = factorization(B)
        for i in range(len(fact)):
            f = fact[i][0]
            if A % f == 0:
                ans += 1
        print(ans)
    
    #print(' '.join(map(str,B)))

Submission status: Accepted

Solution code:
from math import sqrt


def IsPrime(num):
    if num < 2:
        return True
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    sqrtNum = sqrt(num)
    for i in range(3, int(sqrtNum) + 1, 2):
        if num % i == 0:
            return False

    return True


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

    # divisors.sort()
    return divisors


if __name__ == "__main__":
    A, B = map(int, input().split())

    A_list = make_divisors(A)
    B_list = make_divisors(B)

    AB_list = set(A_list) & set(B_list)

    ans = list()
    for i in AB_list:
        if IsPrime(i):
            ans.append(i)

    print(len(ans))

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)
    return divisors

comdiv = [] 
div = make_divisors(A)
for i in div:
  if B % i == 0:
    comdiv.append(i)
#print(comdiv)

def isPrime(n):
  if n < 2:
    return False
  i = 2
  while i*i <= n:
    if n%i == 0:
      return False
    i += 1
  return True

cnt = 0
for i in comdiv:
  if isPrime(i):
    cnt += 1
print(cnt+1)

Submission status: Accepted

Solution code:
import fractions

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
  
a = set(prime_factorize(A))
b = set(prime_factorize(B))
c = a & b

print(len(c) + 1)

Submission status: Accepted

Solution code:
import math
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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

g = gcd(a,b)


arr = []
temp = g
for i in range(2, int(-(-g**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])

print(len(arr)+1)

Submission status: Accepted

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

    if temp!=1 and temp not in arr:
        Cnt += 1
        arr.append(temp)

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

    return Cnt


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

if a < b:
    a, b = b, a
while a % b != 0:
    a, b = b, a % b
# print(b)
N = factorization(b)

print(N+1)

Submission status: Accepted

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

def gcd(x,y):
    while not y == 0:
        tmp = y
        y = x%y
        x = tmp
    return x

import math
def num_prime_factors(n):
    cnt = 0
    m = int(math.sqrt(n)) + 1
    for num in range(2,m):
        if n % num == 0:
            cnt += 1
            while n % num == 0:
                n //= num
    if not n == 1:
        cnt += 1
    return cnt

g = gcd(a,b)
cnt = num_prime_factors(g)
print(cnt+1)

Submission status: Accepted

Solution code:
import math

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

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

    return True

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
    
a, b = map(int, input().split())

set1 = set(make_divisors(a))
# print(set1)

set2 = set(make_divisors(b))
# print(set2)

set3 = set1 & set2
# print(set3)

count = 0
for n in set3:
    # print(n)
    if is_prime(n):
        # print(n)
        count += 1

print(count)

Submission status: Accepted

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


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


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

a_div = list(make_divisors(a))
a_div_pri = []
for num in a_div:
    if is_prime(num):
        a_div_pri.append(num)

a_div_pri.append(1)
ans = 0
for num in a_div_pri:
    if b % num == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#from collections import defaultdict 
import copy
import math
A,B = map(int, input().split())

num = min(A,B)
tmps = {}
p = 2
for p in range(2, math.ceil(num**0.5)+1):

    if A % p == 0 and B % p == 0:
        tmps[p] = True

    if A % (num//p) == 0 and B % (num//p) == 0:
        tmps[num//p] = True

    p += 1

if num != 1 and  A % num == 0 and B % num == 0:
    tmps[num] = True


d = copy.deepcopy(tmps)
for k in tmps.keys():

    if d.get(k, False):
        aaa = copy.deepcopy(d)
        for n in d.keys():
            if k == n:
                continue
            if n > k and n % k == 0:
                aaa.pop(n)
        d = aaa

print(len(d.keys())+1)

Submission status: Accepted

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

c = set(make_divisors(a))
d = set(make_divisors(b))
e = list(c & d)

f = []
for i in range(len(e)):
        if is_prime(e[i]):
            f.append(e[i])
print(len(f) + 1)

Submission status: Accepted

Solution code:

from fractions import gcd
import itertools
import sys
input = sys.stdin.readline


#nの素数判定
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


#nの約数列挙
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 coprime(a, b):
    return gcd(a, b) == 1


def main():
    A, B = map(int, input().split())
    # print(gcd(A, B))
    da = sorted(divisor(A))
    db = sorted(divisor(B))
    cd = []
    for i in da:
        if i in db:
            cd.append(i)

    # print(cd)
    li = []
    # c = itertools.combinations(cd, 2)
    for i in cd:
        if i == 1:
            li.append(i)
            continue

        flg = True
        for c in li:
            if not coprime(i, c):
                flg = False

        if flg:
            li.append(i)

    # print(li)
    print(len(li))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
if a<b:
  a,b=b,a
def gcd(m,n):
  while n!=0:
    m,n=n,m%n
  return m
def div(l):
  division=[]
  for i in range(1,int(l**0.5)+1):
    if l%i==0:
      division.append(i)
      if i!=(l//i):
        division.append(l//i)
  return division
lst=div(gcd(a,b))
cnt=1
for i in range(len(lst)):
  if len(div(lst[i]))==2:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
def find_lcd(A,B):
  if A==1 or B==1:
    return 1
  if A==B:
    return A
  else:
    return find_lcd(min(A,B), abs(A-B))
  
def find_num_prime(X):
  if X==1:
    return 1
  count = 1 # 1
  i=2
  sqrt_org=int(X**0.5)
  while X != 1:
    if i**2 > X:
      count += 1
      break
    if X%i == 0:
      count += 1
      while X%i == 0:
        #print(str(X)+' '+str(i))
        X = int(X/i)
    if i== 2:
      i += 1
    else:
      i += 2
  return count
  
A,B = map(int, input().split())
lcd=find_lcd(A,B)
#print(lcd)
print(find_num_prime(lcd))

Submission status: Accepted

Solution code:
from fractions import gcd

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


def divisor(n):
    i = 1
    xs = []
    while i * i <= n:
        if n % i == 0:
            xs.append(i)
            xs.append(n//i)
        i += 1
    return set(xs)


ad, bd = divisor(A), divisor(B)
xs = list(sorted(ad & bd))

ans = [1]
for x in xs:
    flag = True
    for k in ans:
        if gcd(x, k) != 1:
            flag = False
            break
    if flag:
        ans.append(x)
print(len(set(ans)))

Submission status: Accepted

Solution code:
from math import sqrt

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

#公約数
A,B = map(int,input().split())
M = gcd(A,B)

if M == 1:
    print(1)
    exit()

res = []
x = M
y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x //= y
    y += 1
if x > 1:
    res.append(x)

ans = set(res)
print(len(ans)+1)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
from fractions import gcd
max = gcd(a,b) 
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 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

div_list = make_divisors(max)

count = 1
for i in range(len(div_list)):
#     print(div_list[i])
#     print(is_prime(div_list[i]))
    if is_prime(div_list[i]):
        count += 1

print(count)

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 = map(int,input().split())
A_factors=prime_factorize(A)
B_factors=prime_factorize(B)
B_factors = set(B_factors)
A_factors = set(A_factors)
C = A_factors & B_factors
ans = len(C) + 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import heapq

a,b = (int(i) for i in 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

D = make_divisors(gcd(a,b))
j = {d:True for d in D}

heapq.heapify(D)
ans = []
ans.append(heapq.heappop(D))

for _ in range(len(D)):
    tmp = heapq.heappop(D)
    if j[tmp] == True:
        for d in D:
            if gcd(tmp,d) != 1: j[d] = False
        ans.append(tmp)

print(len(ans))

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def coprime(a, b) : 
    return (gcd(a, b) == 1) 

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

    return sorted(divisors)

def count(arr):
    ans = set()
    for i in arr:
        if i == 1:
            ans.add(i)
            continue
        else:
            flag = 1
            for j in ans:
                if j != 1:
                    if (i % j) == 0:
                        flag = 0
                        break
            if flag == 1:
                ans.add(i)
    return(len(ans))

A,B = list(map(int,input().split()))
gcd_ab = gcd(A,B)
arr = make_div(gcd_ab)
n = len(arr)
print(count(arr))

Submission status: Accepted

Solution code:
def f(n):
    result = set()
    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
            result.add(i)

    if temp != 1:
        result.add(temp)

    return result


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

fa = f(a)
fb = f(b)

print(len(fa & fb)+1)

Submission status: Accepted

Solution code:
import fractions

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

N = fractions.gcd(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

  
if((A-1)*(B-1) == 0):
  print(1)
else:
  print(1 + len(factorization(N)))

Submission status: Accepted

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

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

def count_(upper_num):
    data = [2] + list(range(3,upper_num+1,2))
    idx = 0
    length = len(data)
    while idx < length:
        prime = data[idx]
        data = [d for d in data if (d==prime or d % prime != 0)]
        idx += 1
        length = len(data)
    
    return data

def make_divisors(n):
    divisors = [1]
    i = 2 
    max_int = int(n**0.5)+1
    while n >1:
#         print(n)
        if i >= max_int:
#             print("max")
            divisors.append(n)
            break
        # nを合う数字で割り切れたら、その割った数と商をリストに追加する。
        # nが平方数のとき、同じ数字が2回追加されてしまうので3行したのif文がある
        if n % i == 0:
            divisors.append(i)
            max_int = int((n//i)**0.5)+1
            while n%i == 0:
                n = n//i
                
        i += 1

    divisors = list(set(divisors))
#     divisors.sort()
    return divisors

print(len(make_divisors(gcd(A,B))))

Submission status: Accepted

Solution code:
import math

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

divisors_a = set(make_divisors(a))
divisors_b = set(make_divisors(b))

common_divisors = []
for a in divisors_a:
    if a in divisors_b:
        common_divisors.append(a)

counter = 0
for i in common_divisors:
    if is_prime(i) or i == 1:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
import math as m
import fractions as fr

def is_prime(n): #素数かどうか判定
    if n == 1: return False
    for k in range(2, int(m.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

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   

a, b = map(int, input().split())
g = fr.gcd(a,b)
tb = divisor(g)

count = 1
for i in tb:
    if is_prime(i):
        count += 1

print(count)

Submission status: Accepted

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

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

agcd = 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)

    divisors.sort()
    return divisors

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

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

    return True

x = make_divisors(agcd)
ans = 1
for _x in x:
    ans += is_prime(_x)

print(ans)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def factorize(n):
    f=[]
    p=2
    while p**2<=n:
        while n%p==0:
            n=n//p
            f.append(p)
        p+=1
    if n!=1:
        f.append(n)
    return f

def main():
    a,b=map(int,input().split())
    g=gcd(a,b)
    F=factorize(g)
    print(len(set(F))+1)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def factorization(n):
    d = dict()
    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
            d[i] = cnt
    
    if temp != 1:
        d[temp] = 1
    
    if len(d) == 0:
        d[n] = 1
    
    return d

def main():
    input = sys.stdin.readline
    A, B = map(int, input().split())
    if A == B == 1:
        return 1

    Af = factorization(A,)
    Bf = factorization(B,)
    cnt = 1
    for a in Af.keys():
        if a in Bf.keys():
            cnt += 1

    return cnt

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import fractions
a, b = map(int, input().split())
n = fractions.gcd(a, b)
i = 1
ass = [1]
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)
print(len(set(ass)))

Submission status: Accepted

Solution code:
import fractions

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

# A, B の正の公約数から互いに素となる組み合わせを選ぶとき、最大でいくつ選べる？
# 最大公約数を求める
gcd = fractions.gcd(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)
# 1のケースのみ1を出力する
if f == [[1, 1]]:
    print(1)
else:
    # 要素数＋１が選択可能な個数
    ans = len(f) + 1
    print(ans)

Submission status: Accepted

Solution code:
import math

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

maxp = int(math.sqrt(min(a,b))) + 1

primes = [1]
is_prime = [True] * (maxp + 1)
#print(is_prime)
i = 2
cnt = 1
for i in range(2, maxp+1):
    #print(i)
    if is_prime[i]:
        primes.append(i)
        if a % i == 0 and b % i == 0:
            #print(i)
            cnt += 1
        while a % i == 0:
            a = a // i
        while b % i == 0:
            b = b // i
    j = i * i
    while j <= maxp:
        is_prime[j] = False
        j += i


if a > 1 and b > 1:
    if max(a, b) % min(a, b) == 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import fractions

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


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


c = make_divisors(a)
d = make_divisors(b)
e = []
for i in c:
    if i in d:
        e.append(i)

e.pop(0)
e.sort()

gcd_list = [1]
for i in e:
    count = 0
    for j in gcd_list:
        if fractions.gcd(i, j) != 1:
            break
        else:
            count += 1
        if count == len(gcd_list):
            gcd_list.append(i)

print(len(gcd_list))

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

def coprime(a, b):
    return gcd(a, b) == 1

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

G = gcd(A, B)
l = make_divisors(G)
l.remove(1)
if len(l) == 0:
    print(1)
else:
    c = 1
    for i in range(len(l)):
        for j in range(i):
            if not coprime(l[i], l[j]):
                break
        else:
            c += 1
    print(c)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
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, cnt])

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

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

    return arr

if fractions.gcd(A,B) == 1:
    print(1)
else:
    print(len(factorization(fractions.gcd(A,B)))+1)

Submission status: Accepted

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


def is_dividable(x, d_set):
    for d in d_set:
        if x % d == 0 and d != 1:
            return True

    return False


a, b = map(int, input().split(' '))
divs_a = make_divisors(a)
divs_b = make_divisors(b)

common_div = [x for x in divs_a if x in divs_b]
common_div.sort()

seq = set()
for x in common_div:
    if not is_dividable(x, seq):
        seq.add(x)

# print(seq)
print(len(seq))

Submission status: Accepted

Solution code:
import fractions

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

gcd_ab=fractions.gcd(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

soinnsuu=factorization(gcd_ab)

if gcd_ab == 1:
    ans=1
else:
    ans=len(soinnsuu)+1

print(ans)

Submission status: Accepted

Solution code:
import fractions #fractionsに変更用
import random

A, B = list(map(int, input().split()))
C = fractions.gcd(A,B)
cnt = 1
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

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

D = make_divisors(C)
for i in D:
    if is_prime(i) == True:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# D - Disjoint Set of Common Divisors
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        if 2 not in a:
            a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
                a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


inputNum = list(map(int, input().split()))

resultA = prime_factorize(inputNum[0])
resultB = prime_factorize(inputNum[1])

print(len(set(resultA) & set(resultB)) + 1)

Submission status: Accepted

Solution code:
# from math import factorial
# from collections import defaultdict, deque
#  from heapq import heappush, heappop, heapify

# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# edges = defaultdict(list)
# for _ in range(N - 1):
#     a, b = [int(i) for i in input().split(" ")]
#     edges[a-1].append(b-1)
import math

A, B = [int(i) for i in input().split(" ")]

def solve(n):
    ans, i = [], 1
    while i * i <= n:
        div, mod = divmod(n, i)
        if mod == 0:
            ans.append(i)
            if i != div:
                ans.append(div)
        i += 1
    return list(sorted(ans))  # 順番気にしないならソートせずにより高速

a = solve(A)
b = solve(B)
c = list(sorted(set(a) & set(b)))
# print(c)

ans = []
for i in c:
   for a in ans:
       if a == 1: continue
       if i % a == 0:
          break
   else:
      ans.append(i) 
# print(ans)
print(len(ans))

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 = map(int, input().split())
pa, pb = set(prime_factorize(a)), set(prime_factorize(b))
print(len(list(pa & pb))+1)