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

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

def gdc(A, B):
    if B == 0:
        return A
    else:
        return gdc(B, A % B)

def chk_pn(num):
    flag = True
    if num  <= 3:
        pass
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = False
                break
    return flag

def mk_factor(num):
    max_divisor = int(math.sqrt(num))+1
    divisor = 2
    factor_list = [1]

    while divisor <= max_divisor:
        if num % divisor == 0:
            factor_list.append(divisor)
            num /= divisor
        else:
            divisor += 1
    if num != 1.0:
        factor_list.append(num)
    return factor_list

GDC = gdc(A, B)
#pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]

print(len(set(mk_factor(GDC))))

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

A, B = lr()

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

primes = prime_factorize(min(A, B))
answer = set()
for p in primes:
    if A % p == 0 and B % p == 0:
        answer.add(p)

print(len(answer) + 1) # 1をプラス
# 35

Submission status: Accepted

Solution code:
from fractions import gcd

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

ans = 1

if g % 2 == 0:
  ans += 1
while g % 2 == 0:
  g /= 2

i = 3
while i * i <= g:
  if g % i == 0:
    ans += 1
  while g % i == 0:
    g /= i
  i += 2

if g != 1:
  ans += 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
A,B = [int(i) for i in input().split()]
if A == 1 and B==1:
    print(1)
else:
    ans = 1
    lia = factorization(A)
    lib = factorization(B)
    na = len(lia)
    nb = len(lib)
    a = [0] * na
    b = [0] * nb
    for i in range(na):
        a[i] = lia[i][0]
    for i in range(nb):
        b[i] = lib[i][0]
    a_ = set(a)
    b_ = set(b)
    if na >= nb:
        for i in range(nb):
            if b[i] in a_:
                ans+=1
        print(ans)
        exit()
    else:
        for i in range(na):
            if a[i] in b_:
                ans+=1
        print(ans)
        exit()

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
A,B = [int(i) for i in input().split()]
if A == 1 and B==1:
    print(1)
else:
    ans = 1
    lia = factorization(A)
    lib = factorization(B)
    na = len(lia)
    nb = len(lib)
    a = [0] * na
    b = [0] * nb
    for i in range(na):
        a[i] = lia[i][0]
    for i in range(nb):
        b[i] = lib[i][0]
    a_ = set(a)
    b_ = set(b)
    if na >= nb:
        for i in range(nb):
            if b[i] in a_:
                ans+=1
        print(ans)
        exit()
    else:
        for i in range(na):
            if a[i] in b_:
                ans+=1
        print(ans)
        exit()

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



N,M=map(int,input().split())
L=make_divisors(gcd(N, M))
ANS=[]
for i in L:
  FLG = True
  for j in L[1:]:
    if j > i:
      break
    if i != j and i % j == 0:
      FLG = False
      break
  if FLG:
    ANS.append(i)
      

print(len(ANS))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(100000000)
mod = 1000000007
"""
#N,K,Mが入力
    n,k,m=LI() 
    #N
    #x1 y1
    #.  .
    #xn ynが入力
    N=I()
    p=LIR(N)
    print(n,k,m,p)
"""
############################## ユニオン木(union tree) ###################################
#uf=UnionFind(n)と使う
# print(uf.roots())
# print(uf.all_group_members())
class UnionFind:
    def __init__(self, n):
        self.n=n
        self.par = [-1 for i in range(self.n+1)]
        self.rank = [0 for i in range(self.n+1)]#素集合でないとrankは意味がなさそう,素集合であればrank kには少なくとも2^k要素がある。
    
    # 検索
    def find(self, x):
        # if self.par[x] == x:
        if self.par[x] <0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n+1) if self.find(i) == root]

    #すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.par) if x<0]

    #グループの数を返す
    def group_count(self):
        return len(self.roots())

    #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {int(r):self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    

#辞書やタプルで使えるようにクラスを継承 l = ['A', 'B', 'C', 'D', 'E']とかを想定
class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        self.n = len(labels)
        labels=[0]+labels#n+1と合わせるため
        self.par = [-1 for i in range(self.n+1)]
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
        self.rank = [0 for i in range(self.n+1)]#素集合でないとrankは意味がなさそう,素集合であればrank kには少なくとも2^k要素がある。

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union_label(self, x, y):
        super().union(self.d[x], self.d[y])

    #def size(self, x):
    #    return super().size(self.d[x])

    def same_label(self, x, y):
        return super().same(self.d[x], self.d[y])

    def members_label(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n+1) if self.find(i) == root]

    def roots_label(self):
        return [self.d_inv[i] for i, x in enumerate(self.par) if x<0]
    
    def all_group_members_label(self):
        return {int(r):self.members_label(r) for r in self.roots_label()}


########### nの約数を全て求める ##################
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
########## 素因数分解のリスト
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(int(i))
        i += 1
    if n > 1:
        table.append(int(n))
    return table

############## a,bの最大公約数 ##################


#こっちのほうがいい？
import fractions

def comdiv(a,b):
    ta=set(divisor(a))
    tb=set(divisor(b))
    t=ta & tb
    return list(t)

def resolve():
    a,b=LI()
    buf=fractions.gcd(a,b)
    t=prime_decomposition(buf)
    #t=comdiv(a,b)
    #uf=UnionFindLabel(t)
    #print(uf.all_group_members_label())
    s=set(t)
    print(len(s)+1)
    #print(uf.all_group_members_label())
    """
    ans=set()
    for i in t:
        buf=set(divisor(i))
        if len(buf)>2:
            l={1,i}
            buf=buf-l
        ans=ans | buf
    """


    return

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """12 18"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """420 660"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 2019"""
        output = """1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	A,B = MI()
	def gcd(A,B):
		if(B != 0):
			A,B=B,A%B
			return gcd(A,B)
		else:
			return A

	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,B=max(A,B),min(A,B)
	gc = gcd(A,B)
	if(gc==1):
		print(1)
	else:
		print(len(factorization(gc))+1)

main()

Submission status: Accepted

Solution code:
def prime_factors(n: int) -> list:
    tmp = n
    i = 2
    res = []
    while i*i <= n:
        if tmp%i==0:
            res.append(i)
            while tmp%i==0:
                tmp //= i
        i += 1
    # add remaining factor
    if tmp > 1:
        res.append(tmp)
    return res


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

    g = gcd(A, B)
    factors = prime_factors(g)
    print(len(factors)+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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 = list(map(int, input().split()))
print(len(set(prime_factorize(fractions.gcd(a, b))))+1)

Submission status: Accepted

Solution code:
def prime(n):
    res =set()
    while n% 2==0:
        res.add(2)
        n //= 2
    i  = 3
    while i*i <= n:
        if n % i==0:
            res.add(i)
            n //= i
        else:
            i += 2
    if n != 1:
        res.add(n)
    return res
a,b = map(int,input().split())
a = prime(a)
b = prime(b)
print(len(a&b)+1)

Submission status: Accepted

Solution code:
import fractions

def div(n):
  l =[]
  for i in range(1,n+1):
    if n%i ==0:
      l.append(i)
  return l

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

A,B = list(map(int,input().split()))
maxy = fractions.gcd(A,B)

l2 = prime_decomposition(maxy)
print(len(l2) + 1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc142/tasks/abc142_d
# これは,A,Bの最大公約数を見つけてからそれを素因数分解し、累乗の底の個数＋1が答えとなる。

from fractions import gcd


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない

    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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, B = list(map(int, input().split()))


G = gcd(A, B)
ans = len(factorization(G)) + 1
print(ans)

Submission status: Accepted

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

count=1
C_copy=C
n=2
while n**2<=C:  #C==1になるまでCを割る方針では、Cに大きい素因数が含まれている場合にTLEする
   if C_copy==1:
      break

   flag=False
   while C_copy%n==0:
      C_copy//=n
      flag=True
   if flag:
      count+=1
      n=n+1 if n==2 else n+2
   else:
      n=n+1 if n==2 else n+2

if C_copy!=1:
   count+=1

print(count)

Submission status: Accepted

Solution code:
def primes(n):  #エラストテネスのふるい
   is_prime = [True] * (n + 1)
   is_prime[0] = False
   is_prime[1] = False
   for i in range(2, int(n**0.5) + 1):
      if not is_prime[i]:
         continue
      for j in range(i * 2, n + 1, i):
         is_prime[j] = False
   return [i for i in range(n + 1) if is_prime[i]]

from fractions import gcd
import math
A,B=map(int,input().split())
C=gcd(A,B)
prime_numbers=primes(int(math.sqrt(C))+1)

count=1
for p in prime_numbers:
   if C==1:
      break

   flag=False
   while C%p==0:
      C//=p
      flag=True
   if flag:
      count+=1
      p=p+1 if p==2 else p+2
   else:
      p=p+1 if p==2 else p+2

if C!=1:
   count+=1

print(count)

Submission status: Accepted

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

from fractions import gcd
import math
A,B=map(int,input().split())
C=gcd(A,B)
prime_numbers=primes(int(math.sqrt(C))+1)

if C==1:
   print(1)
else:
   count=1

   for p in prime_numbers:
      if C==1:
         break
      
      flag=False
      while C%p==0:
         C//=p
         flag=True
      if flag:
         count+=1
         p=p+1 if p==2 else p+2
      else:
         p=p+1 if p==2 else p+2
   
   if C!=1:
      count+=1

   print(count)

Submission status: Accepted

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

if C==1:
   print(1)
else:
   count=1
   C_copy=C
   n=2
   while n**2<=C:
      flag=False
      while C_copy%n==0:
         C_copy//=n
         flag=True
      if flag:
         count+=1
         n=n+1 if n==2 else n+2
      else:
         n=n+1 if n==2 else n+2
   
   if C_copy!=1:
      count+=1

   print(count)

Submission status: Accepted

Solution code:
import fractions

a, b = map(int, input().split())
gcd = fractions.gcd(a, b)
count = 1
for i in range(2, int(gcd ** 0.5) + 1):
    if gcd % i == 0:
        count += 1
    while gcd % i == 0:
        gcd //= i
if gcd != 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
import math,sys
sys.setrecursionlimit(1000000)
def mygcd(x,y):
    if x<y:x,y=y,x
    if y==0:return x
    return mygcd(y,x%y)
def is_prime(n):
    if n==1:return True
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return False
    return True
A,B = map(int,input().split())
gcd = mygcd(A,B)
C = []
for i in range(1,gcd+1):
    if i*i>gcd:break
    if gcd%i==0:
        C.append(i)
        if i!=gcd//i:
            C.append(gcd//i)
cnt = 0
for c in C:
    if is_prime(c):cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import defaultdict

A, B = map(int, input().split())
x = gcd(A, B)
d = defaultdict(int)

d[1]=1
for i in range(2, int(x**0.5)+1):
    while x%i==0:
        x//=i
        d[i]+=1
if x!=1:
    d[x]+=1

ans = len(d.keys())
print(ans)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    factors = set([1])
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            factors.add(i)
            n //= i
    factors.add(n)

    return factors


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

fa = prime_factorize(a)
fb = prime_factorize(b)

print(len(fa & fb))

Submission status: Accepted

Solution code:
from math import sqrt

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

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

print(len(set(d(A)) & set(d(B)))+1)

Submission status: Accepted

Solution code:
def Euclid(a,b):
  r = a % b
  if r == 0:
    return b
  return Euclid(b,r)
import fractions

a,b = map(int,input().split())
#c = Euclid(a,b) if a > b else Euclid(b,a)
c = 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 c == 1:
  print(1)
else:
  print(len(factorization(c))+1)

Submission status: Accepted

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

    # divisors.sort()
    return divisors

def eratosthenes(divs):
    dn = len(divs)
    array = [1 for _ in range(dn)]
    for i in range(1,dn):
        if array[i] == 0:
            continue
        for j in range(i+1, dn):
            if divs[j] % divs[i] == 0:
                array[j] = 0
    return array

from fractions import gcd
a,b = map(int, input().split())
divs = sorted(make_divisors(min(a,b), max(a,b)))
array = eratosthenes(divs)

print(sum(array))
# print(divs)
# print(array)

Submission status: Accepted

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

N = gcd(A,B)
#print(N)
ans = set()
for i in range(2,int(1e6 + 100)):
  if N == 1:
    break
  while N % i == 0:
    ans.add(i)
    N /= i
if N > 1:
  ans.add(N)
  
print(len(ans) + 1)

Submission status: Accepted

Solution code:
import fractions

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

x = fractions.gcd(a,b)
ans = []

i = 2
y = int(x**0.5)
while True:
    if x%i == 0:
        x //= i
        ans.append(i)
    elif i == y:
        ans.append(x)
        break
    elif x == 1:
        break
    else:
        i += 1

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

Submission status: Accepted

Solution code:
import fractions

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

x = fractions.gcd(a,b)
ans = []

i = 2
y = int(x**0.5)
for j in range(10000000):
    if x%i == 0:
        x //= i
        ans.append(i)
        i = 2
        y = int(x**0.5)
    elif i == y:
        ans.append(x)
        break
    else:
        i += 1

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

n = gcd(A, B)
ans = 1

tmp = n
l = []
for i in range(2, int(-(-n**0.5//1))+1):
    if tmp % i == 0:
        l.append(i)
        while tmp % i == 0:
            tmp //= i

if tmp != 1:
    l.append(tmp)

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

if len(l) == 1 and l[0] == 1:
    print(1)
else:
    print(len(l) + 1)

Submission status: Accepted

Solution code:
import math
a,b = map(int,input().split(" "))
def gcd(a,b):
    if a < b:
        a,b = b,a
    while b > 0:
        a,b = b, a % b
    return a


def factorize(num):
    res = list()
    n = num
    while num % 2 == 0:
        num //= 2
        res.append(2)

    for i in range(3,int(math.sqrt(n))):
        while num % i == 0:
            num //= i
            res.append(i)
    
    if num >= 2:
        res.append(num)
    return res
    

g = gcd(a,b)
print(len(set(factorize(g))) + 1)

Submission status: Accepted

Solution code:
import math
import fractions

def is_prime(num):
  for i in range(2, int(math.sqrt(num))+1):
    if num % i == 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

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

g = fractions.gcd(A, B)
f = prime_factorize(g)
print(len(set(f))+1)

Submission status: Accepted

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


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


a, b = map(int, input().split())
q = prime_factorize(gcd(a, b))
# print(q)
print(len(q) + 1)

Submission status: Accepted

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

def f(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

def g(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
 
ans=set(f(a))&set(f(b))
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
from fractions import gcd

A,B = [int(zz) for zz in 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

x = gcd(A,B)

print(len(set(prime_factorize(x)))+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())
div1 = make_divisors(A)
# print(div1)
div2 = make_divisors(B)
nums = list(set(div1).intersection(set(div2)))
# print(nums)
nums = [x for x in nums if is_prime(x)]
# print(nums)
cnt = len(nums)
if cnt > 1:
    print(cnt)
else:
    print(1)

Submission status: Accepted

Solution code:
import fractions
a,b=map(int,input().split())
ab_gcd=fractions.gcd(a,b)
cd=[1]
tmp=int(ab_gcd**0.5)+1
if ab_gcd==1:
    print(1)
    exit()

for i in range(2,tmp+1):
   while ab_gcd%i==0:
        ab_gcd//=i
        cd.append(i)
if ab_gcd!=1:
    cd.append(ab_gcd)
cd=set(cd)
print(len(cd) if len(cd)!=1 else 2)

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
from collections import Counter

read = lambda: sys.stdin.readline().rstrip()

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

class Solution(object):
    def disjoint_set_of_common_divisors(self, A, B):
        return len(Counter(prime_factorize(gcd(A, B))).keys())+1

def main():
    
    A0, B0 = map(int, read().split())
    #A0 = tuple(map(int, read().split()))

    res = Solution().disjoint_set_of_common_divisors(A0, B0)

    print(res)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def prime_factors(n):
    res = set()
    while n % 2 == 0:
        res.add(2)
        n //= 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            res.add(i)
            n //= i
        else:
            i += 2
    if n != 1:
        res.add(n)
    return res

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

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
from collections import Counter

read = lambda: sys.stdin.readline().rstrip()

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

def disjoint_set_of_common_divisors(A, B):

    return len(Counter(prime_factorize(gcd(A, B))).keys())+1

def main():
    
    A0, B0 = map(int, read().split())
    #A0 = tuple(map(int, read().split()))

    res = disjoint_set_of_common_divisors(A0, B0)

    print(res)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    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]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)

Submission status: Accepted

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


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


A_factor = set(prime_factorization(A))
B_factor = set(prime_factorization(B))
print(len(A_factor & B_factor) + 1)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+2):
        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==[] and n != 1:
        arr.append(n)
 
    return arr
 
a, b = map(int, input().split())
 
an = set(factorization(a))
bn = set(factorization(b))
print(len(an&bn) + 1)

Submission status: Accepted

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

g = fractions.gcd(A,B)
h = math.floor(math.sqrt(g))
D = {1:1}
for i in range(2,h+1):
    while g%i == 0:
        D[i] = D.get(i,0) + 1
        g //= i
    if g == 1:
        break
if g > 1:
    D[g] = D.get(g,0) + 1

print(len(D))

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

from functools import reduce
from fractions import gcd
import collections

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

aaa = reduce(gcd,[a,b])

c = collections.Counter(prime_factorize(aaa))
cnt = 0
for i in c:
  cnt += 1
print(cnt+1)

Submission status: Accepted

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

def is_prime(n): # 素数判定
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return True



A, B = map(int, input().split())
A_d = divisor(A)
B_d = divisor(B)
n_d = []
for i in A_d:
    if i in B_d:
        n_d.append(is_prime(i))
print(sum(1 for i in n_d if i is True))