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:
# 入力を2つの数値として扱う
a, b = map(int, input().split())

# 最大公約数を求める関数(ユークリッド互除法)
def gcd(i, j):
    while j != 0:
        i, j = j, i % j
    return i

# 公約数のリストを返す関数(最大公約数の約数)
def divisor(n):
    i = 1
    ret = []
    while i * i <= n:
        if n % i == 0:
            ret.append(i)
            ret.append(n//i)
        i += 1
    ret = list(set(ret))
    ret.sort()
    return ret

# 互いに素(最大公約数が1)の場合Trueを返す関数
def coprime(i, j):
    return gcd(i, j) == 1

# 最大公約数を求める
g = gcd(a, b)

# 公約数のリストを求める
dl = divisor(g)

# 公約数を調べる
cnt = 1
# 1より大きい約数について
while cnt < len(dl):
    lc = 1
    # 次の約数と比較
    while cnt + lc < len(dl):
        # for debug:print(str(dl[cnt]) + ',' + str(dl[cnt + lc]))
        # 素でない場合は削除
        if not coprime(dl[cnt], dl[cnt + lc]):
            dl.remove(dl[cnt + lc])
            lc -= 1
        lc += 1
    cnt += 1

# 答えの出力
print(len(dl))

Submission status: Accepted

Solution code:
import sys,math

def input():
    return sys.stdin.readline()[:-1]
def yakusuu(N):
    P = [1,N]
    for k in range(2,math.floor(math.sqrt(N))+1):
        if N % k == 0:
            P.append(k)
            P.append(N//k)
    return P
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

def main():
    A, B = map(int,input().split())
    C = sorted(list(set(yakusuu(A))&set(yakusuu(B))))

    if len(C) == 1:
        print(1)
        exit(0)
    D = [1]
    for k in range(1,len(C)):
        f = 1
        for l in range(k):
            if gcd(C[k],C[l]) != 1:
                f = 0
                break
        if f == 1:
            D.append(C[k])
    print(len(D))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from collections import Counter


def factorize(n: int):
    d = Counter()
    m = 2

    while m * m <= n:
        while n % m == 0:
            n //= m
            d[m] += 1

        m += 1

    if n > 1:
        d[n] += 1

    return d

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

a, b = li()

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

Submission status: Accepted

Solution code:
from fractions import gcd
import math
import numpy as np
N = list(map(int, input().split()))
g = gcd(N[0], N[1])

def factorize(g):
  factor = []
  for i in range(2, int(np.sqrt(g))+2):
    if g % i != 0:
      continue
    while g % i == 0:
      g //= i
    factor.append(i)
  if g != 1:
    factor.append(g)
  return factor
print(len(factorize(g))+1)

Submission status: Accepted

Solution code:
from fractions import gcd


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

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

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

    return arr


a, b = list(map(int, input().split()))
g = gcd(a, b)
if g == 1:
    print('1')
else:
    print(len(factorization(g))+1)

Submission status: Accepted

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

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_list=factorization(a)
b_list=factorization(b)

a_new=[a[0] for a in a_list]
b_new=[b[0] for b in b_list]

if a_new[0]==b_new[0]==1:
    ans=0

for i in a_new:
    if i in b_new:
        ans += 1

print(ans)

Submission status: Accepted

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

def divisors(n):
  ret=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      if i!=n//i:
        ret.append(n//i)
  return ret
    
def is_prime(n):
  if n==1 or n==2 or n==3:
    return True
  else:
    for i in range(2,int(n**0.5)+1):
      if n%i==0:
        return False
    return True

a,b=map(int,input().split())
g=gcd(a,b)
divs=divisors(g)
ans=0
for val in divs:
  if is_prime(val)==True:
    ans+=1
print(ans)

Submission status: Accepted

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

_a, _b = map(int, input().split())


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

    return a


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

    return sorted(dvlist)


def chker(a, b):
    a, b = min(a, b), max(a, b)
    mindiv = get_divisor(a)
    shdvlist = [item for item in mindiv if b % item == 0]
    if len(shdvlist) < 3:
        print(len(shdvlist))
        return

    slist, shdvlist = [shdvlist[1]], shdvlist[1:]
    for item1 in shdvlist:
        flg = 0
        for item2 in slist:
            if item1 % item2 == 0:
                flg = 1
                break

        if flg == 0:
            slist.append(item1)

    print(len(slist) + 1)


chker(_a, _b)

Submission status: Accepted

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


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

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

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

    return arr


def solve(A: int, B: int):
    while A % B:
        tmp = B
        B = A % B
        A = tmp
    if B == 1:
        print(1)
    else:
        ans = factorization(B)
        print(len(ans)+1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(x,y):
  n,m = min(x,y), max(x,y)
  while n!=0:
    n, m = m%n, n
  
  return m

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

A, B = list(map(int, input().split(" ")))
print(1+len(set(prime_factorization(gcd(A, B)))))

Submission status: Accepted

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

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

def prime(n):
    if n % 2 == 0:
        return 2
    elif n % 3 == 0:
        return 3
    else:
        for i in range(2, int(n**(1/2))+1):
            if n % i == 0:
                return i
        return n

def div(n):
    divs = []
    tmp = n
    while True:
        if tmp == 1:
            return divs
        ret = prime(tmp)
        if ret != 0:
            divs.append(ret)
            tmp = tmp // ret
        else:
            divs.append(ret)
            break

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

Submission status: Accepted

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

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

A, B = map(int, input().split())
g = gcd(A,B)
print(len(factorize(g))+1)

Submission status: Accepted

Solution code:
import fractions
A, B = map(int, input().split())
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 len(arr)+1

if c == 1:
    print(1)
else:
    print(factorization(c))

Submission status: Accepted

Solution code:
import fractions

N, P = [int(x) for x in input().strip().split(" ")]

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



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

xx = prime_decomposition(fractions.gcd(N, P))
print(len(xx) + 1)

Submission status: Accepted

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

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

As = list(set(map(int, prime_decomposition(A))))
Bs = list(set(map(int, prime_decomposition(B))))
print(len([a for a in As if a in Bs]))

Submission status: Accepted

Solution code:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    gcd = fractions.gcd(a, b)
    cnt = 1
    for i in range(2, int(gcd ** 0.5) + 1):
        while True:
            if gcd % i == 0:
                cnt += 1
                while True:
                    if gcd % i == 0:
                        gcd //= i
                    else:
                        break
            else:
                break
    print(cnt if gcd == 1 else cnt + 1)



if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    gcd = fractions.gcd(a, b)
    cnt = 1

    for i in range(2, int(gcd ** 0.5) + 1):
        if gcd % i == 0:
            cnt += 1
            while True:
                if gcd % i == 0:
                    gcd //= i
                else:
                    break
    print(cnt + 1 if gcd != 1 else cnt)


if __name__ == '__main__':
    slove()

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 = []
    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

x, y = map(int, input().split())
list_x = make_divisors(x)
list_y = make_divisors(y)
#listの一致するところをとってくる
list_xy = set(list_x) & set(list_y)

a = 0
for i in list_xy:
    if is_prime(i) == True:
        a = a + 1
    else:
        continue
print(a+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
a = []
b = []
import random

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


for i in range(1, int(A**(1/2))+1):
    if A % i == 0:
        a.append(i)
        a.append(A//i)
for i in range(1, int(B**(1/2))+1):
    if B % i == 0:
        b.append(i)
        b.append(B//i)

a = set(a)
b = set(b)
a = a & b

ans = 0
for i in a:
    if is_prime(i):
        ans += 1
print(ans+1)

Submission status: Accepted

Solution code:
import fractions
a, b = map(int, input().split())
c=fractions.gcd(a, b)
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
d=list(set(prime_decomposition(c)))
ans=len(d)+1
print(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())
# 素因数分解して重複削除
a2 = list(set(prime_factorize(a)))
b2 = list(set(prime_factorize(b)))
# 連結
con = a2 + b2
# 重複のみ抽出
ans = [x for x in set(con) if con.count(x) > 1]
# 公倍数1を考慮
print(len(ans) + 1)

Submission status: Accepted

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


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


gcd = _gcd(a, b)
i, cnt = 2, 1
while i * i <= gcd:
    flag = 0
    while gcd % i == 0:
        flag = 1
        gcd //= i
    if flag:
        cnt += 1
    i += 1
if gcd != 1:
    cnt += 1
print(cnt)

Submission status: Accepted

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

a, b = map(int, input().split())
n = GCD(a,b)
i = 2
table = []
while i * i <= n:
    while n % i == 0:
        n = n // i
        table.append(i)
    i += 1
if n > 1:
    table.append(n)
print(len(set(table))+1)

Submission status: Accepted

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

gcdv = gcd(a, b)

prime_cnt = Counter()
n = gcdv
for i in range(2, int(gcdv ** 0.5) + 2):
    while n % i == 0:
        n //= i
        prime_cnt[i] += 1

prime_cnt[n] += 1
prime_cnt[1] += 1

print(len(prime_cnt.keys()))

Submission status: Accepted

Solution code:
import fractions

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

if gcd > 1:
  fact = 2
  tmp = gcd
  while(fact * fact <= gcd):
    if tmp % fact == 0:
      ans += 1
      while(tmp % fact == 0):
        tmp //= fact
    fact += 1
  if tmp > 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return

#B
def B():
    n, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

#D
def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

Solution code:
A = [int(i) for i in input().split()]

prime_num = [[],[]]

prime_num[0].append(1)
prime_num[1].append(1)

for i in range(2):
    a = 2
    n = A[i]
    while A[i] >= a*a:
        if n%a == 0:
            prime_num[i].append(a)
            n /= a
        else:
            a+=1
    prime_num[i].append(n)
    

#print(prime_num)
print(len(set(prime_num[0])&set(prime_num[1])))

Submission status: Accepted

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

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


A, B = map(int, input().split())
G = gcd(A, B)
d = [1]

for i in range(2, int(math.sqrt(G))+1):
  if G % i == 0:
    d.append(i)
    while G % i == 0:
      G /= i
      
if G != 1:
  d.append(G)

print(len(d))

Submission status: Accepted

Solution code:
from fractions import gcd

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

ans = 0
i = 2
check = False
while c != 1:
    #print(c,i)
    while c % i == 0:
        #print('a')
        c = c // i
        check = True
    i = i + 1
    if check:
        ans += 1
    check = False
    if i > 1000000:
        print(ans+2)
        exit()
print(ans + 1)

Submission status: Accepted

Solution code:
def prime_factor(num):
	count = 0
	bak = num
	for i in range(2, num):
		if(i*i>num):
			break
		if(bak%i == 0):
			count += 1
		while(bak%i == 0):
			bak = bak//i
	if (bak > 1):
		count += 1
	return count



def calgcd(a, b):
	if(a%b == 0):
		return b
	else:
		return calgcd(b, a%b)



A, B = map(int, input().split())
gcd = calgcd(A, B)
print(prime_factor(gcd) + 1)

Submission status: Accepted

Solution code:

from fractions import gcd

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

def prime_factrization(n):
    exponent = 0
    while n%2 == 0:
        exponent += 1
        n //= 2
    if exponent == 0:
        a = []
    else:
        a = [[2,exponent]]
    
    q = 1
    while q*q <= n:
        q += 2
        if n%q != 0:
            continue
        exponent = 0
        while n%q == 0:
            exponent += 1
            n //= q
        a.append([q,exponent])
        
    if n != 1:
        a.append([n,1])
    return a

if x == 1:
    print(1)
else:
    a = prime_factrization(x)
    print(len(a)+1)

Submission status: Accepted

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


A, B = map(int, input().split())
a = set(prime_factorize(A))
b = set(prime_factorize(B))
ans = 0
for ap in a:
    if ap in b:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def factorization(n):
    if n == 1:
        return []
    else:
        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 not arr:
            arr.append(n)
        return arr


input_values = list(map(int, input().split()))
print(len(list(set(factorization(input_values[0])) & set(factorization(input_values[1])))) + 1)

Submission status: Accepted

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

MAX_NUM = 10**6
is_prime = [True] * MAX_NUM
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(2, MAX_NUM):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, MAX_NUM, i):
            is_prime[j] = False

def f(x):
    res = {}
    for p in primes:
        if x % p == 0:
            res[p] = 0
            while x % p == 0:
                res[p] += 1
                x //= p
    if x > 1:
        res[x] = 1
    return res

def solve(a, b):
    p = f(gcd(a, b))
    return len(p) + 1

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

Submission status: Accepted

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

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


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


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


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import fractions
import itertools

a, b = list(map(int, input().split()))
c = min(a, b)
d = max(a, b)


def factorize(n: int) -> list:
    # 試し割り法
    f_list = []
    while n % 2 == 0:
        f_list.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            f_list.append(f)
            n //= f
        else:
            # 偶数はすでにチェックしているので+2ずつカウントアップ
            f += 2

    if n != 1:
        f_list.append(n)
    return f_list


a_list = factorize(a)
b_list = factorize(b)

common = (set(a_list) & set(b_list)) | {1}
count = len(common)

print(count)

Submission status: Accepted

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


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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math as m
import fractions

A, B = list(map(int, input().split()))
#A , B = 12, 18

def sieve_of_eratosthenes(n):
    candidate = [1 for i in range(n+1)]
    candidate[0] = 0
    candidate[1] = 0
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

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

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

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



# print(num)

g = fractions.gcd(A,B)
primes = []
num = 1

if True:
    i = 2
    while i * i <= g:
        if (g % i == 0):
            cnt = 0
            while g % i == 0:
                cnt = cnt + 1
                g = g // i
            primes.append([i, cnt])
        i = i + 1
    if (g != 1):
        primes.append([g, 1])
print(len(primes)+1)

Submission status: Accepted

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

def isprime(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 divi(n):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      res.append(i)
      if i != n // i:
        res.append(n // i)
  return res

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

def main():
  a, b = na()
  gcd_ = gcd(a, b)
  ans = 1
  for d in divi(gcd_):
    if isprime(d):
      ans += 1
  print(ans)

main()

Submission status: Accepted

Solution code:
import fractions

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

x = fractions.gcd(A, B)

ans = 1

for i in range(2, int(x**0.5)+2):
    n = 0
    while x % i == 0:
        x //= i
        n += 1
    if n != 0:
        ans += 1
if x != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
def euqlid(x,y):
    while x % y != 0:
        tmp = x % y
        x = y
        y = tmp
    return y
a, b = map(int, input().split())
if a < b:
    tmp = a
    a = b
    b = tmp
k = euqlid(a, b)
sum = 0
i = 2
if k == 1:
    print(1)
    exit()
while i <= math.sqrt(k):
    flag = False
    while k % i == 0:
        k = k // i
        flag = True
    if flag:
        sum += 1
    i += 1
if i <= k:
    sum += 1
print(sum + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import fractions


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


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

    gcd = fractions.gcd(a, b)
    table = prime_factorization(gcd)
    print(len(table) + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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


gcd = GCD(A, B)
divs = prime_decomposition(gcd)
print(1 + len(divs))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
A, B = (int(i) for i in input().split())

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

gcd = mygcd(A, B)
temp = gcd
count = 1
for i in range(2, int(-(-gcd**0.5//1))+1):
    if temp%i == 0:
        cnt = 0
        while temp%i ==0:
            cnt +=1
            temp //= i
        count +=1
if temp != 1:
    count +=1

print(count)

Submission status: Accepted

Solution code:
import sys
import fractions
input = sys.stdin.readline
A, B = (int(i) for i in input().split())

gcd = fractions.gcd(A, B)
temp = gcd
count = 1
for i in range(2, int(-(-gcd**0.5//1))+1):
    if temp%i == 0:
        cnt = 0
        while temp%i ==0:
            cnt +=1
            temp //= i
        count +=1
if temp != 1:
    count +=1

print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
A, B = (int(i) for i in input().split())

cd = [1]
factors = {}
temp = A
for i in range(2, int(-(-A**0.5//1))+1):
    if temp%i==0:
        cnt = 0
        while temp%i==0:
            #print(temp)
            cnt+=1
            temp //= i
        factors[i] = 1
if temp!=1:
    factors[temp] = 1
#print(factors)
temp = B
for i in range(2, int(-(-B**0.5//1))+1):
    if temp%i==0:
        cnt = 0
        while temp%i==0:
            cnt+=1
            temp //= i
        #print(i)
        if i in factors:
            factors[i] = 2
        else:
            pass
if temp!=1:
    if temp in factors:
        factors[temp] = 2
#print(factors)
count = 1
for k, v in factors.items():
    if v==2:
        count+=1

print(count)