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:
#!/usr/bin/env python3
import sys
# from math import gcd

def gcd(a, b):
    while b: a, b = b, a % b
    return abs(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

# print(factorization(14)) 

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
    # print(pa)
    if a != 1:
        ct +=1
    print(ct+1)
    
    return


# Generated by 1.1.6 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:
from fractions import gcd
def prime_factorize_dict(n):
    d = dict()
    while not n & 1:
        d[2] = d.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            d[f] = d.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n] = d.get(n, 0) + 1
    return d

print(len(prime_factorize_dict(gcd(*map(int, input().split())))) + 1)

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    a,b = readInts()
    from fractions import gcd
    g = gcd(a,b)
    #print(g)
    i = 2
    A = defaultdict(int)
    while i * i <= g:
        if g % i == 0:
            A[i] += 1
            g //= i
        else:
            i += 1
    A[g] += 1
    ans = 1
    for k,v in A.items():
        if k != 1:
            ans += 1
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline().rstrip


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

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

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


def main():
    a, b = map(int, input().split())
    a = factorization(a)
    b = factorization(b)
    l = a & b
    print(len(l))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter

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

gcd_ab = gcd(a, b)


def prime_factorize(n):
    res = 0
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m+1 if m == 2 else m+2
    if n>1:
        d[n] += 1
    return d


if gcd_ab == 1:  # コーナーケース
    print(1)
    exit()

# (素因数分解の素因数の個数)+1が答え
prime_d = prime_factorize(gcd_ab)
print(len(prime_d)+1)

Submission status: Accepted

Solution code:
def factorization(n): # https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
    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())
a, b = max(a,b), min(a,b)

r = -1
while r != 0:
    r = a%b
    a, b = b, r
# a = 最大公約数

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

Submission status: Accepted

Solution code:
import math
def make_divisors(m, n):
    divisors = []
    numi = min(m, n)
    numa = max(m, n)
    for i in range(1, int(math.sqrt(numi)) + 1):
        if numi % i == 0:
            if numa % i == 0:
                divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != numi // i and numa % (numi // i) == 0:
                divisors.append(numi // i)
    return sorted(divisors)

a, b = map(int, input().split())
lista = make_divisors(a, b)
listb = [1]
lista.pop(0)
while len(lista) > 0:
    listb.append(lista[0])
    lista = [i for i in lista if i % lista[0] != 0]
print(len(listb))

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt


def prime_factorize(n):
    result = []
    for i in range(2, int(sqrt(n)) + 1):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


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

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

# 高速素因数分解
def factorize(n):
    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
n = gcd(A, B)
ans = factorize(n)
if ans[0][0] == 1:
    print(1)
else:
    print(len(ans)+1)

Submission status: Accepted

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

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

c=fact(a)
d=fact(b)
e=[1]

  
for i in range(len(c)):
  if c[i]  in d:
    e.append(c[i])

e=set(e)    
print(len(e))

Submission status: Accepted

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

def gdc(A,B):
    if A < B:
        A,B = B,A
    if B==0:
        return A
    else:
        A,B=B,A%B
        return gdc(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(len(set(pn_factor)))

Submission status: Accepted

Solution code:

"""nを素因数分解"""
"""2以上の整数n => [(素因数, 指数), ...]の2次元リスト"""


def factorization(n):
    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

import fractions
a, b = map(int, input().split())
li = factorization(fractions.gcd(a, b))

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

Submission status: Accepted

Solution code:
from collections import Counter
from fractions import gcd
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
g = gcd(a, b)
l = [1]
while g % 2 == 0:
    l.append(2)
    g /= 2
f = 3
while f * f <= g:
    if g % f == 0:
        l.append(f)
        g /= f
    else:
        f += 2
if g != 1:
    l.append(int(g))
cnt = Counter(l)
print(len(cnt))

Submission status: Accepted

Solution code:
from math import factorial as fact
import math
import fractions
import sys
import itertools
import numpy as np
from collections import Counter
import datetime
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1

def combinations(n,r):
	return list(itertools.combinations(n,r))

def all_sets(num_list):
	subsets=[]
	for i in range(2,len(num_list) + 1):
		for c in combinations(num_list, i):
			subsets.append(c) 
	return subsets

#公約数の列挙
def ch(x1):
	cf=[]
	for i in range(2,math.sqrt(x1)+1):
		if x1 % i==0:
			cf.append(i)
	return cf

def CountOneRoots(x,y):
	#x:縦，y:横
	return fact(x+y)/fact(x)/fact(y)

# 素因数分解
def factorization(n):
	tmp=n
	count=0
	for i in range(2,int(n**0.5)+2):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
				cnt+=1
				tmp//=i
			count+=1
	if tmp!=1:
		count+=1

	return count
			


A,B=input2()
gcd=fractions.gcd(A,B)
# ch=ch(gcd)
print(factorization(int(gcd))+1)

Submission status: Accepted

Solution code:
import fractions
import math
from collections import deque
A,B = list(map(int,input().split()))
gcd = fractions.gcd(A,B)
def gcd_another(N):
    R = deque()
    for i in range(1,math.ceil(int(N**0.5))+1):
        if N % i == 0:
            R.append(i)
            if i != N // i:
                R.append(N//i)
    R = list(R)
    R.sort()
    return R
C = gcd_another(gcd)
C.pop(0)
total = 1
while C != []:
    i = C[0]
    C = [j for j in C if j % i != 0]
    total += 1
print(total)

Submission status: Accepted

Solution code:
import random

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

count = 0

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

    # divisors.sort()
    return divisors

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True


AL = make_divisors(A)
BL = make_divisors(B)

CS = set(AL) & set(BL)

for p in CS:
    if is_prime3(p):
        count += 1

print(count + 1) # +1 は1を含めるため

Submission status: Accepted

Solution code:
from fractions import gcd
from math import floor, sqrt

a, b = [int(x) for x in input().split()]
c = gcd(a, b)

d_list = [1]
d = 2
stop = floor(sqrt(c))
while True:
    temp, mod = divmod(c, d)
    if mod == 0:
        d_list.append(d)
        c = temp
        stop = floor(sqrt(c))
    else:
        d += 1
    
    if stop < d:
        d_list.append(c)
        break

ans = len(set(d_list))
print(ans)

Submission status: Accepted

Solution code:
import fractions
A,B = map(int,input().split())
x = fractions.gcd(A,B)
pf = {}
for i in range(2,int(x**0.5)+2):
  while x%i == 0:
    pf[i] = pf.get(i,0) +1
    x //= i
if x > 1:
  pf[x] = 1
print(len(pf)+1)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
from fractions import gcd
from numpy import sqrt
m = gcd(a,b)
cnt = 1
for i in range(2, int(sqrt(m))+1):
    div = False
    while m%i == 0:
        div = True
        m = m//i
    if div:
        cnt += 1
    if m == 1:
        break
if m > 1:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# solution
import io
import math
import heapq
import bisect

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}

nim, mike = map(int,input().split())
print(len(f(nim) & f(mike) | {1}))

Submission status: Accepted

Solution code:
p,q=map(int,input().split())
if q>p:
  p,q=q,p
  
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
  
def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a
  
g=gcd(p,q)
res=prime_factorize(g)
print(len(res)+1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])

    prime = [1]
    for p in res:
        for _ in range(p[1]):
            prime.append(p[0])

    return prime


def resolve():
    a, b = map(int, input().split())
    A = prime_factorization(a)
    B = prime_factorization(b)

    res = set(A) & set(B)
    print(len(res))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def prime_factor(n):
    factors = []
    for i in range(2, int(n**0.5)+1):
        count = 0
        while n % i == 0:
            count += 1
            n /= i
        if count != 0:
            factors.append((i, count))
    if n != 1:
        factors.append((n, 1))
    return factors
a, b = map(int, input().split())
apf = prime_factor(a)
bpf = prime_factor(b)
print(len(set(i[0] for i in apf)&set(i[0] for i in bpf))+1)

Submission status: Accepted

Solution code:
import math
A, B = map(int, input().split())
if B < A:
    A, B = B, A
a = []
while A % 2 == 0:
    a.append(2)
    A //= 2
f = 3
while f * f <= A:
    if A % f == 0:
        a.append(f)
        A //= f
    else :
        f += 2
if A != 1:
    a.append(A)
ans = 0
for i in set(a):
    if B % i == 0:
        ans += 1
print(ans+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

a,b = map(int,input().split())
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

ab = gcd(a,b)
primes = prime_factor(ab)
print(len(primes)+1)

Submission status: Accepted

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


def prime_factorization(n):
    from collections import Counter
    counter = Counter()

    if n < 2:
        return counter

    for i in range(2, int(n ** 0.5) + 1):
        if i * i > n:
            break

        while n % i == 0:
            counter[i] += 1
            n //= i

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

    return counter


x = prime_factorization(A)
y = prime_factorization(B)

z = set(x.keys()) & set(y.keys())
print(len(z) + 1)

Submission status: Accepted

Solution code:
# Problem D - Disjoint Set of Common Divisors

import fractions

# 約数を列挙する関数
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 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

# input
A, B = map(int, input().split())
C = fractions.gcd(A, B)
if A==1 or B==1:
    print(1)
elif C==1:
    print(1)
else:
    arr = factorization(C)
    print(len(arr) + 1)

Submission status: Accepted

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

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

G = gcd(A, B)
P = primeCount(G)

ans = 1 + len(P.keys())
print(ans)

Submission status: Accepted

Solution code:
import math
A, B = map(int,input().split())
def yakusuu(N):
    P = set([1,N])
    for k in range(2,math.floor(math.sqrt(N))+1):
        if N % k == 0:
            P.add(k)
            P.add(N//k)
    return P
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
C = sorted(list(yakusuu(A)&yakusuu(B)))
N = len(C)
if N == 1:
    print(1)
else:
    ans = 0
    for k in range(N):
        f = 1
        for l in range(k):
            if gcd(C[k],C[l]) != 1:
                f = 0
                break
        ans += f
    print(ans)

Submission status: Accepted

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

def mygcd(a, b):
    if a < b:
        return mygcd(b, a)
    elif b == 0:
        return a
    else:
        return mygcd(b, a % b)

gcd = mygcd(A, B)

import math

pfac = {}
gcd_tmp = gcd
for p in range(2, int(math.sqrt(gcd)) + 1):
    if gcd_tmp < 2: break
    if gcd_tmp % p == 0:
        i_p = 0
        while gcd_tmp % p == 0:
            gcd_tmp //= p
            i_p += 1
        #
        pfac[str(p)] = i_p
else:
    if gcd_tmp > 1: pfac[str(gcd_tmp)] = 1
    
# print("#", pfac)
        
print(1 + len(pfac))

Submission status: Accepted

Solution code:
import math
A,B=map(int,input().split())
X=math.sqrt(min(A,B))
L=[]
for i in range(1,int(X)+1):
	if A%i==0:
		L.append(i)
		L.append(A//i)
L=set(L)
L=sorted(L)
S=[]
for i in L:
	if B%i==0:
		S.append(i)
ans=1
for i in S:
	if i==1:continue
	count=0
	for j in range(2,int(math.sqrt(i))+1):
		if i%j==0:
			count+=1
			break
	if count==0:
		ans+=1
print(ans)

Submission status: Accepted

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

from collections import Counter
#最大公約数を素因数分解する
def factorize(n):
  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

fs = factorize(g) # "1"以外の公約数
print(len(fs) + 1) # 公約数"1"を足す

Submission status: Accepted

Solution code:
def make_prime_factors_compress(n: int):
    """自然数nの素因数を列挙した圧縮済みリストを出力する
    計算量：O(sqrt(N))
    入出力例：156 -> [(2, 2), (3, 1), (13, 1)]
    """
    prime_factors = []
    for k in range(2, int(n**0.5) + 1):
        cnt = 0
        while n % k == 0:
            cnt += 1
            n = n // k
        if cnt != 0:
            prime_factors.append((k, cnt))
    if n != 1:
        prime_factors.append((n, 1))
    return prime_factors

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a: int, b: int) -> int:
    """a, bの最小公倍数(least common multiple: LCM)を求める
    計算量: O(log(min(a, b)))
    """
    return (a * b) // gcd(a, b)

  
a, b = map(int, input().split())
gcd_ = gcd(a, b)
print(len(make_prime_factors_compress(gcd_)) + 1)

Submission status: Accepted

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

import fractions
g = fractions.gcd(a, b)

import math

def div(m):
    d = {}
    temp = int(math.sqrt(m))+1
    for i in range(2, temp):
        while m%i== 0:
            m //= i
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    if d == {}:
        d[m] = 1
    else:
        if m in d:
            d[m] += 1
        elif m != 1:
            d[m] =1
    return d

d = div(g)
#print(d)
if 1 not in d:
    ans = len(d)+1
else:
    ans = 1
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.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(1000000)
mod = 1000000007

def solve():
    def f(n):
        res = set([1])
        i = 2
        m = n
        while i**2 <= n:
            while m%i == 0:
                res.add(i)
                m //= i
            i += 1
        res.add(m)
        return res

    a,b = LI()
    fa = f(a)
    fb = f(b)
    l = fa&fb
    print(len(l))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

from collections import Counter
def factorize(n):
    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

fs = factorize(g)

print(len(fs) + 1)

Submission status: Accepted

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

GCD = gcd(a,b)
ans = 1
for i in range(2, int(GCD ** 0.5) + 1):
    if GCD%i == 0:ans += 1
    while GCD%i == 0:
        GCD //= i
if GCD != 1:ans += 1
print(ans)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
from fractions import gcd
import math
ab_gcd = gcd(a,b)
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return [1,n]
    else:
        factor.append(n)
        return factor
res = trial_division(ab_gcd)
print(len(set(res+[1])))

Submission status: Accepted

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

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

aa = set(pf(a))
bb = set(pf(b))
ans = aa & bb

print(len(ans) + 1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
import fractions
gcd = fractions.gcd(A, B)
#gcd
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
# n == 1のとき、[1, 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
if gcd == 1:
    print(1)
else:
    ans = len(factorization(gcd)) + 1
    print(ans)

Submission status: Accepted

Solution code:
import math
import collections
#import sys
#input = sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]


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 gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

    
a,b=MI()
g=gcd(a,b)
pg=list(set(prime_factorize(g)))
print(len(pg)+1)

Submission status: Accepted

Solution code:

#最大公約数を求める
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a % b)

#nの素因数分解を行い、リスト[[素因数,指数],....]を返す
# 2020 = 2^2 * 5^1 * 101^1
#[[2,2],[5,1],[101,1]
def prime_factorize(n):
    #返す配列
    res = []
    for i in range(2,n+1):
        #指数
        ex = 0
        # √Nまで行う
        if i * i > n:
            break
        if n % i != 0:
            continue
        #iで割り続ける
        while ( n % i == 0):
            ex += 1
            n /= i
        #その結果を追加
        res.append([i,ex])
    #最後に残った数について、1でなければ素数なのでリストに加える
    if n != 1:
        res.append([int(n),1])

    return res

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

#最大公約数を求める
G = gcd(A,B)

#素因数分解
pf = prime_factorize(G)

#素因数のの個数 + 1 が答え
print(len(pf) +1)

Submission status: Accepted

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

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

    if arr==[]:
        arr.append([n, 1])
    #arr.append([1, 1])
    return arr
if a == 1 or b == 1:
    print(len(factorization(gcd)))
    quit()
print(len(factorization(gcd)) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt


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

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

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

    return arr


def main():
    A, B = map(int, input().split())
    C = gcd(A, B)
    if (A == 1 or B == 1):
        print(1)
        exit(0)
    if (C == 1):
        print(1)
        exit(0)
    arr = factorization(C)
    # print(arr)
    print(len(arr) + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt


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

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

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

    return arr


def main():
    A, B = map(int, input().split())
    C = gcd(A, B)
    if (C == 1):
        print(1)
        exit(0)
    arr = factorization(C)
    # print(arr)
    print(len(arr) + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def factrize(x):
    f = {}
    if x == 1:
        return f
    tmp = x
    i = 2
    while i**2 <= tmp:
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp = tmp//i
        if cnt > 0:
            f[i] = cnt
        i += 1
    if tmp != 1 or f == {}:
        f[tmp] = 1
    return f

from fractions import gcd
A, B= map(int, input().split())
G = gcd(A, B)
dict = factrize(G)
print(1+len(dict))

Submission status: Accepted

Solution code:
import fractions
A,B = map(int,input().split())
GCD = fractions.gcd(A,B)
if GCD == 1:
    print(1)
    exit()
    
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

Bunkai = factorization(GCD) 
print(len(Bunkai) + 1)

Submission status: Accepted

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

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

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

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

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

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

    return arr

#factorization(24)
## [[2, 3], [3, 1]]
##  24 = 2^3 * 3^1

g = gcd(a,b)
#gcd_list = make_divisors(g)
bunkai = factorization(g)

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

Submission status: Accepted

Solution code:
from fractions import gcd
A,B=map(int,input().split())
x=gcd(A,B)
prime=set()
prime.add(1)
for i in range(2,int(x**0.5)+1):
    while x%i==0:
        prime.add(i)
        x//=i
if x!=1:
    prime.add(x)
print(len(prime))