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:
A, B = map(int,input().split())

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


def calculate(a,b):
    s1 = yinshufenjie(a)
    s2 = yinshufenjie(b)

    set1 = set()
    set2 = set()
    for key in s1.keys():
        set1.add(key)

    for key in s2.keys():
        set2.add(key)

    a = set1 & set2
    print(len(a)+1)


calculate(A,B)

Submission status: Accepted

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)
def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g
def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g
def lcm(arr):
    l = lcm_core(arr[0],arr[1])
    for i in range(2,len(arr)):
        l = lcm_core(l,arr[i])
    return l
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 isprime(p):
    x = 2
    while x*x <= p:
        if p%x == 0:
            return False
        x += 1
    return True

A, B = map(int, input().split())
ans = 0
for i in set(divisor(A)) & set(divisor(B)):
    if isprime(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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


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


a, b = map(int, read().split())
cnt = 1
for n in set(prime_decomposition(b)) & set(prime_decomposition(a)):
    if is_prime(n):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
A, B = [int(x) for x in input().split()]


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

a = prime_decomposition(A)
b = prime_decomposition(B)

a = set(a)
b = set(b)
ab = a.intersection(b)
ab.add(1)

print(len(ab))

Submission status: Accepted

Solution code:
import numpy as np


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

lisa = prime_factorize(a)
lisb = prime_factorize(b)
lis = set(lisa) & set(lisb)
lis.add(1)
lis = sorted(list(lis))
devil = (max(a,b)/lis[-1])
if len(prime_factorize(devil)) == 1:
  if min(a,b) % devil == 0:
    lis.append(devil)
print(len(set(lis)))

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

    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(pn_factor)
print(len(set(pn_factor)))

Submission status: Accepted

Solution code:
import sys
if sys.version_info.minor < 5:
    from fractions import gcd
else:
    from math import gcd
import math

DEBUG = False

A, B = map(int, input().split())
g = gcd(A, B)
if DEBUG:
    print("gcd(A, B): {}".format(g))

ans = [1]
i= 2
temp = g
while i <= int(-(-g**0.5//1))+1:
    if DEBUG:
        print("i: {}, g: {}".format(i, g))

    if temp % i == 0:
        if DEBUG:
            print("This is a cd of A and B.")
        ans.append(i)

    while temp % i == 0:
        temp //= i

    i += 1

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

if DEBUG:
    print(ans)

print(len(ans))

Submission status: Accepted

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

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

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

  return arr

set_a = set(factorize(a))
set_b = set(factorize(b))

set_ab = set(set_a) & set(set_b)
ans = len(set_ab) + 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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 = map(int, input().split())
    a = set(make_divisors(A))
    b = set(make_divisors(B))
    ans = 0
    union_ab = a & b
    #print(union_ab)
    tmp = [1]
    for s in union_ab:
        if s >= 4 and s%2 == 0:
            continue
        if len(make_divisors(s)) == 2:
            tmp.append(s)
    #print(tmp)
    ans = len(tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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
print(len(pf)+1)

Submission status: Accepted

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

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

ans = 1
if not n % 2: ans += 1

while not n % 2:
    n //= 2

i = 3

while i <= n**0.5:
    if not n % i: ans += 1
    while not n % i:
        n //= i
    i += 2

if 1 < n: ans += 1
print(ans)

Submission status: Accepted

Solution code:
import fractions

def main():
    A,B=map(int,input().split())
    gcd = fractions.gcd(A, B)
    ans=[1]
    sqrt=gcd**0.5
    
    #gcdの素因数の個数を求める
    
    while gcd%2==0:
        gcd=gcd//2
        ans.append(2)
    f=3
    while f*f<=gcd:
        if gcd%f==0:
            gcd=gcd//f
            ans.append(f)
        else:
            f+=2
    
    if gcd!=1:
        ans.append(gcd)
        
    print(len(set(ans)))

if __name__=="__main__":
    main()

Submission status: Accepted

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

    def prime_factorize(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])

        arr.append([1, 1])

        return arr

    a = prime_factorize(A)
    set_a = set(i for i, j in a)
    b = prime_factorize(B)
    set_b = set(i for i, j in b)

    ans = len(set_a & set_b)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    def prime_factorize(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])


        return arr

    cd = gcd(A, B)
    ans = len(prime_factorize(cd)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	A,B = inputMap()

	As = factorize(A)
	As = list(set(As))
	bs = factorize(B)
	bs = list(set(bs))

	ans = 0
	for i in As:
		if i in bs:
			ans += 1

	print(ans+1)

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

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def prime(n):
    memo = []
    for i in range(2,int(n**0.5)+1):
        while n%i == 0:
            memo.append(i)
            n //= i
    if n != 1:
        memo.append(n)
    return memo
        
    
a,b = map(int,input().split())    

aa = list(set(prime(a)))
bb = list(set(prime(b)))

count = 1

for i in aa:
    if i in bb:
        count += 1

print(count)

Submission status: Accepted

Solution code:
a,b = list(map(int,input().split()))
ad,bd = [],[]
for i in range(1,int(a**(1/2)) + 1):
    if a%i == 0:
        ad.append(i)
        ad.append(a//i)
for i in range(1,int(b**(1/2)) + 1):
    if b%i == 0:
        bd.append(i)
        bd.append(b//i)
cd = list(set(ad) & set(bd))
ans = []
def prime(n):
    if all(n%i!=0 for i in range(2,int(n**(1/2))+1)):
        return True
    else:
        return False
for num in cd:
    if prime(num):
        ans.append(num)
print(len(ans))

Submission status: Accepted

Solution code:
import fractions
A, B = map(int, input().split())
gcd = fractions.gcd(A, B)
ans = 1
sqrt = gcd ** 0.5
for i in range(2, int(sqrt) + 2):
    if gcd % i == 0:
        ans += 1
        while True:
            gcd //= i
            if gcd % i != 0:
                break
if sqrt < gcd:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import math
a,b = map(int,input().split())
n = gcd(a,b)
if n == 1:
    print(1)
    exit()
count = 1
for i in range(2,math.ceil(math.sqrt(n))+1):
    if n % i == 0:
        count += 1
        while n % i == 0:
            n //= i
if n > 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
import math
import fractions

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

g = fractions.gcd(A,B)

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

ans = 1

for i in range(2,math.floor(math.sqrt(g))+1):
    if g % i == 0:
        ans += 1
        while g % i == 0:
            g = g//i
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 = map(int, input().split())

fac_A = factorization(A)
fac_B = factorization(B)

prime_A = [f[0] for f in fac_A]
prime_B = [f[0] for f in fac_B]

if 1 in prime_A: prime_A.remove(1)
if 1 in prime_B: prime_B.remove(1)
common = set(prime_A) & set(prime_B)
print(len(common)+1)

Submission status: Accepted

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

def euclid( A, B ):
  a = A
  b = B
  r = a % b
  while r != 0:
    a = b
    b = r
    r = a % b
  return 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 )

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

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

    return len( set( arr ) )

D = factorization( euclid( A, B ) )

print( D + 1 )

Submission status: Accepted

Solution code:
import math
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 ( n!=1 ) and ( arr==[] ):
        arr.append(n)

    return set( arr )

a = factorization(A)
b = factorization(B)
cnt = 0
for i in a:
  if i in b:
    cnt += 1

print( cnt + 1 )

Submission status: Accepted

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

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    i = 1
    while i <= math.sqrt(n):
        if n % i == 0:
            divisors.append(i)
            if i != math.sqrt(n):
                divisors.append(n // i)
        i += 1

    return divisors

def test_prime(n):
    if n == 1:
        return True
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            return False
        i += 1
        
    return True
    
a_d = make_divisors(A)
b_d = make_divisors(B)

common_d = set(a_d) & set(b_d)

prime = 0

for c in common_d:
    if test_prime(c):
        prime += 1

print(prime)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
import fractions
A,B = map(int,input().split())
if A == 1 or B == 1:
    print(1)
else:
    def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
        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
    c = fractions.gcd(A,B)
    arr = factorization(c)
    print(len(arr)+1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from fractions import gcd
def prime_fact(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 list(pf)
def main():
    a,b=map(int,input().split())
    print(1+len(prime_fact(gcd(a,b))))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
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

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 main():
    a,b=map(int,input().split())
    a_s,b_s=set(make_divisors(a)),set(make_divisors(b))
    c_s=a_s&b_s
    ans=[]
    c=list(c_s)
    c.sort()
    ans=1
    for cc in c:
        if is_prime(cc):
            ans+=1
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

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


def prime_factor(n):
    d = set()
    for i in range(2, n + 1):
        if i * i > n:
            break
        while n % i == 0:
            d.add(i)
            n //= i
            
    if n != 1:
        d.add(n)
    return d

a = prime_factor(A)
b = prime_factor(B)
print(len(set(a) & set(b)) + 1)

Submission status: Accepted

Solution code:
import fractions
a,b=map(int,input().split())
s=fractions.gcd(a,b)
cnt={1}
if s%2==0:
    cnt.add(2)
    while s%2==0:
      s//=2
for i in range(3,int(s**0.5)+1,2):
    if s%i==0:
        cnt.add(i)
        while s%i==0:
            s//=i
print(len(cnt)+(s>1))

Submission status: Accepted

Solution code:
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 list(set(a))

import fractions
A,B=map(int,input().split())
gcd=fractions.gcd(A,B)
print(len(f(gcd)))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc142/tasks/abc142_d
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 nC2(n):
    return n * (n - 1) // 2

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

A = set(prime_factorize(a))
B = set(prime_factorize(b))

common = A & B
common.add(1)
ans = len(common)
print(ans)

Submission status: Accepted

Solution code:
A,B = (int(x) for x in input().split())
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors
a = make_divisors(A)
b = make_divisors(B)
c = a & b
count = 1
if 2 in c:
    count += 1
for x in c:
    if x % 2 == 1:
        if len(make_divisors(x)) == 2:
            count += 1
print(count)

Submission status: Accepted

Solution code:
import fractions

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

x = fractions.gcd(A, B)

C = []

def cal(i):
    for j in range(2, int(-(-i**0.5//1))+1):
        while True:
            if i%j == 0:
                i //= j
                C.append(j)
            else:
                break
    if i != 1:
        C.append(i)
        
    return set(C)

print(1+len(cal(x)))

Submission status: Accepted

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

    
    return arr

 
print(len(factorization(k))+1)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

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までの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

# """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
# print(factorization(m))
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

a,b = myinput()
if a==1 and b==1:
    print(1)
    exit()

da = factorization(a)
db = factorization(b)
# print(da)
# print(db)

ls_a = []
for i in da:
    ls_a.append(i[0])

ls_b = []
for i in db:
    ls_b.append(i[0])

# print(ls_a)
# print(ls_b)

ls = list( set(ls_a) & set(ls_b) )
ans = len(ls) + 1
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    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


def main():
    a, b = map(int,input().split())
    print(len(set(prime_factorize(gcd(a, b)))) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd
def prime_factorize(n):
    res = []
    for i in range(2, int(n**0.5)+1):
        if n % i != 0:continue
        ex = 0
        while n % i == 0:
            ex += 1
            n = n//i
        res.append((i, ex))
    if n != 1:res.append((n, 1))
    return res
def main():
    A, B = map(int, input().split())
    g = gcd(A, B)
    res = prime_factorize(g)
    ans = len(res) + 1
    print(ans)
if __name__ == "__main__":
    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 = map(int, input().split())
a_prime = set(prime_factor(a))
b_prime = set(prime_factor(b))
ab_prime = list(a_prime & b_prime)
print(len(ab_prime)+1)

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def gcd(a,b): # 最大公約数を求める
  while b:
    a,b=b,a%b
  return abs(a)
  
def solve(A:int, B:int):
  a=gcd(A,B)
  ap=a
  ct=0
  x=2
  if a%x==0:
    ct+=1
    while a%x==0:
      a=a//x
  
  x=3
  while x*x<ap+1:
    if a%x==0:
      ct+=1
      while a%x==0:
        a=a//x
    x+=2
  
  if a!=1:
    ct+=1
  print(ct+1)
  
  return

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

if __name__=="__main__":
  main()

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
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
yakua = make_divisors(a)
yakub = make_divisors(b)
s = set(yakua) & set(yakub)
ans = []
for i in list(s):
	if is_prime(i):
		ans.append(i)
print (len(ans)+1)

Submission status: Accepted

Solution code:
from collections import Counter

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

    counter_a = Counter(prime_factorize(a))
    counter_b = Counter(prime_factorize(b))

    c_a = list(counter_a.keys())
    c_b = list(counter_b.keys())

    count = len(set(c_a) & set(c_b))

    print(count+1)

if __name__ == '__main__':
    main()