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

def dev(a):
    li = []
    i = 1
    while(i*i<=a):
        if a%i==0:
            li.append(i)
            li.append(a//i)
        i+=1
    return li

#def prime(i):
    


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

c = gcd(a,b)
d = dev(c)
d.sort()
e=str(d)
for i in range(1,len(d)):
    if d[i] != 1:
        for j in range(i+1,len(d)):
            if d[j]%d[i]==0:
                d[j] = 1
            
            
ans = 1
for i in range(len(d)):
    if d[i] != 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from fractions import gcd


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

    return divisors


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

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

    return True


A, B = map(int, input().split(' '))
N = gcd(A, B)
divisors = make_divisors(N)
# print(N)
# print(divisors)

# divisors.sort()
# print(divisors)

cnt = 0
for n in divisors:
    if is_prime(n):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import random
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)


#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass

#n以下の素数列挙(O(n log(n))
def primes(n):
    is_prime = [True] * (n + 100)
    is_prime[0] = False
    is_prime[1] = True
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False

    return is_prime

def is_prime(n):
    if n == 1:
        return True
    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)
d = divisor(g)
d.sort()

res = 0

#isp = primes(g)
#print(isp)

for e in d:
    if is_prime(e):
        res += 1

print(res)

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

GCD = gcd(A, B)
print(len(set(prime_factorize(GCD)))+1)

Submission status: Accepted

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

# A の約数
div1 = set()
for i in range(1, int(A ** 0.5) + 1):
    if A % i == 0:
        div1.add(i)
        if i != A // i:
            div1.add(A // i)
# B の約数
div2 = set()
for i in range(1, int(B ** 0.5) + 1):
    if B % i == 0:
        div2.add(i)
        if i != B // i:
            div2.add(B // i)

div = div1 & div2

cnt = 1
for d in list(div):
    if d == 1:
        continue
    flg = True
    for i in range(2, int(d ** 0.5) + 1):
        if d % i == 0:
            if i in (div-{d}):
                flg = False
                break
    if flg:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import math
import fractions

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

n = fractions.gcd(a, b)

cd = []
for i in range(1, math.ceil(math.sqrt(n) + 1)):
    if n % i == 0:
        if n // i == i:
            cd.append(i)
        else:
            cd.append(i)
            cd.append(n // i)

cd.sort()

ans = 0
for i in range(len(cd)):
    for j in range(i + 1):
        if j == i:
            continue
        if cd[j] > 1 and cd[i] % cd[j] == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

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()
cnt = 0
num = 1
for i in range(len(divisors)):
    if num == 1:
        cnt += 1
        num *= divisors[i]
    elif gcd(num, divisors[i]) == 1:
        cnt += 1
        num *= divisors[i]

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
A,B=np.array(list(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
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
    
C=np.array(prime_factorize(gcd(A,B)))
print(len(np.unique(C))+1)

Submission status: Accepted

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')

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

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

c=gcd(a,b)

def pride(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)
	
	
d=pride(c)

print(len(d)+1)

Submission status: Accepted

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

def isp(n):
  if n < 4:
    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())
N = gcd(max(A, B), min(A, B))
D = md(N)

ans = 0

for d in D:
  if isp(d):
    ans += 1
    
print(ans)

Submission status: Accepted

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

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

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

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

    da = make_divisors(A)
    db = make_divisors(B)
    cds = set(da) & set (db)
    P = prime_factorize(max(cds))
    P.append(1)
    c = collections.Counter(P).keys()
    x = cds & set(c)
    print(len(x))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
A, B = map(int,input().split())
D = 2
ans = 1
A_l = []
B_l = []
MAX = max(A, B)
q_MAX = int(MAX ** (1/2))
for i in range(2, q_MAX+1):
    if A % D == 0:
        while True:
            if A % D != 0:
                break
            A //= D
        A_l.append(D)
    if B % D == 0:
        while True:
            if B % D != 0:
                break
            B //= D
        B_l.append(D)
    if i == q_MAX:
        A_l.append(A)
        B_l.append(B)
    if A == B == 1:
        break
    D += 1
for a in A_l:
    if a in B_l:
        ans += 1
print(ans)

Submission status: Accepted

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

def gcd(p, q):
    if p < q:
        p, q = q, p
    while q != 0:
        p, q = q, p % q
    return p

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

res = factorization(gcd(a, b))
if res[0][0] == 1:
    ans = 1
else:
    ans = len(res) + 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

A, B = read_int()

# 約数列挙 return set
def divisor(n):
    res = []
    i = 1
    while i**2 <= n:
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
        i += 1
    return res

def gcd(a, b):
    if a > b:
        a, b = b, a
    while b % a != 0:
        a, b = b % a, a
    return a

# 素数判定 return bool
def is_prime(n):
    i = 2
    while i**2 <= n:
        if n % i == 0: return False
        i += 1
    return True

def solve():
    ans = 0

    g = gcd(A, B)
    koubai = divisor(g)

    for n in koubai:
        if is_prime(n):
            ans += 1
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
import collections

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
ac = collections.Counter(prime_factorize(A))
#print(prime_factorize(A))
bc = collections.Counter(prime_factorize(B))
keylist = set(ac.keys()) | set(ac.keys())
#keylist.add(set(bc.keys()) )
#print(keylist)
#print(ac,bc)
tmp=0

#print(ac[3])
dlist=[]
for key in keylist:
    if ac[key] > 0 and bc[key] > 0:
        dlist.append([key,min(ac[key],bc[key])])
    #tmp+= max(ac[key],bc[key] )

#print(dlist)
cnt=0
print(len(dlist)+1)
#for i in range(len(dlist)):
#    cnt+=pow(2,dlist[i][1])

#print(cnt-1)

Submission status: Accepted

Solution code:
from fractions import gcd


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

print(len(set(prime_factorize(gcd(A, B)))) + 1)

Submission status: Accepted

Solution code:

def genDivisor(v):
    i=2
    ds=[]
    while i*i<=v:
        if v%i==0:
            ds.append(i)
            ds.append(v//i)
        i+=1
    return ds

x,y=map(int,input().split(" "))

dx=genDivisor(x)
if x>1:
    dx.append(x)
dy=genDivisor(y)
if y>1:
    dy.append(y)

xny=sorted(list(set(dx).intersection(set(dy))))

N=len(xny)
count=1
for i in range(N):
    needToDel=False
    for j in range(i):
        if xny[i]%xny[j]==0:
            needToDel=True
            break
    if needToDel==False:
        count+=1
print(count)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
A, B = map(int,input().split(' '))
if A < B:
  A,B = B,A
while A%B != 0:
  A,B = B,A % B
gcd = B
if gcd == 1:
  print(1)
  exit()
else:
  ans = set(prime_factorize(gcd))
  print(len(ans)+1)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7
import fractions
import math

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

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

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

A, B = MAP()
yakusu = make_divisors(fractions.gcd(A, B))
count = 1
for yy in yakusu:
    if is_prime(yy):
        count += 1
print(count)

Submission status: Accepted

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

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

GCD = gcd(a,b)

fac = factorization(GCD)

if fac[0][0] == 1:
    print(1)
else:
    print(len(factorization(GCD))+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
# from math import gcd

def divisor(n):
    div = set()
    for i in range(1, n // 2 + 2):
        d, m = n // i, n % i
        if m == 0:
            div.add(i)
            div.add(d)
        if d < i:
            break
    return sorted(list(div))


a, b = map(int, input().split())
divs = divisor(gcd(a, b))
collect = []
for d in divs:
    if d == 1 or d == 2:
        collect.append(d)
    else:
        for ci in collect[::-1]:
            if ci != collect[0] and d % ci == 0:
                break
        else:
            collect.append(d)
print(len(collect))

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
  
x, y = map(int,input().split())
x_pr = prime_factorize(x)
y_pr = prime_factorize(y)
z = set(x_pr) & set(y_pr)
print(len(z)+1)

Submission status: Accepted

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

a, b = map(int, input().split())
ab = prime_factorize(fractions.gcd(a, b))
AB = []
for i in ab :
	if i in AB : continue
	AB.append(i)
print(len(AB) + 1)

Submission status: Accepted

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

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

Af = collections.Counter(factorize(A))
Bf = collections.Counter(factorize(B))

Ak = Af.keys()
Bk = Bf.keys()

print(len(set(Ak) & set(Bk))+1)

Submission status: Accepted

Solution code:
import collections

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 = (int(i) for i in input().split())
a = collections.Counter(prime_factorize(A))
b = collections.Counter(prime_factorize(B))

c = []
for i in a.keys():
    if i in b.keys():
        c.append(i)
#print(c)

print(len(c)+1)

Submission status: Accepted

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

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

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

N = gcd(A, B)
if N == 1:
  print (1)
  sys.exit()

D = make_divisors(N)
L = []
for i in D[1:]:
  for j in L:
    if i % j == 0:
      break
  else:
    L.append(i)
print (len(L)+1)

Submission status: Accepted

Solution code:
import fractions

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(' ')))
maxKouyaku = fractions.gcd(A, B)
#print(maxKouyaku)
#print(*factorization(maxKouyaku))
if maxKouyaku == 1:
    print(1)
else:
    print(len(factorization(maxKouyaku)) + 1)

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
a=gcd(A,B)
li=[]
while a%2==0:
    li.append(2)
    a//=2
waru=3
while waru*waru<=a:
    if a%waru==0:
        li.append(waru)
        a//=waru
    else:
        waru+=2
if a!=1:
    li.append(a)
print(len(set(li))+1)

Submission status: Accepted

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


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

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

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

    return arr
a, b = map(int, input().split(' '))
gc = gcd(a, b)
r = []
r = factorization(gc)
if r[0][0] == 1:
    print(1)
else:
    print(len(r)+1)

Submission status: Accepted

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

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    return set(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)

    # divisors.sort()
    return set(divisors)


G=list(make_divisors(A) & make_divisors(B))
G=sorted(G)

for i,g in enumerate(G):
    if g==1:
        continue
    for j,g_right in enumerate(G[i+1:]):
        if g_right%g == 0:
            G.remove(g_right)
print(len(G))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC142 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().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

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

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

P = [1] + primes(10**6)
f = defaultdict(lambda : 0)
for i in P:
    f[i] = 1
a,b = LI()
A,B = make_divisors(a),make_divisors(b)
ans = 0
fa = defaultdict(lambda : 0)
fb = defaultdict(lambda : 0)

for i in A:
    fa[i] = 1
for i in B:
    fb[i] = 1

ans = 0
lst = []
p = []
for i in A:
    if fa[i] and fb[i]:
        if f[i]:
            ans += 1
            p.append(i)
        else:
            lst.append(i)
for i in lst:
    for j in p:
        if gcd(i,j) != 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

    divisors.sort()
    return divisors


A, B = map(int, input().split())
divided_1 = min(A, B)
divided_2 = max(A, B)

divisors = make_divisors(divided_1)
cd = []
for d in divisors:
  if divided_2 % d == 0:
    cd.append(d)

res = []
for e in cd:
  flg = True
  for i in range(1, len(res)):
    r = res[i]
    if e % r == 0:
      flg = False
      break
  if flg:
    res.append(e)

print(len(res))

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
def cf(x1,x2):
    cf=[]
    cf.append(1)
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

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

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

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

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

    return arr

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

result = factorization(gcd(a,b))
ans = len(result)
if not result[-1][0] == 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 最大公約数GCD(x,y)
def GCD(x,y):
    x,y=max(x,y),min(x,y)
    if x%y==0:
        return y
    else:
        return GCD(y,x%y)

def divide(g,p):
    if g%p!=0:
        return g
    if g%p==0:
        global n
        n+=1
        while g%p==0:
            g//=p
        return g

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

n=1 # gの素因数の個数

if g>=2:
    g=divide(g,2)
p=3 # 最初の奇素数
while g>1 and p<1000000:
    g=divide(g,p)
    p+=2
if g>1:
    n+=1
print(n)

Submission status: Accepted

Solution code:
a,b = sorted([int(s) for s in input().split()])
def p(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

ls = [s[0] for s in p(a)]
p = 1

for i in ls:
  if b % i == 0:
    p += 1
if a == 1:
  print(1)
else:
	print(p)

Submission status: Accepted

Solution code:
import collections
import fractions
a, b = input().split()
A = int(a)
B = int(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


GCB = fractions.gcd(A, B)

C = collections.Counter(prime_factorize(GCB))

print(len(C) + 1)

Submission status: Accepted

Solution code:

import math


def div(x):
    divs = []
    divs_append = divs.append
    for i in range(1, int(math.sqrt(x)) + 1):
        if x % i == 0:
            divs_append(i)
            if i != x // i:
                divs_append(x // i)

    return set(divs)


def is_prime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True


A, B = map(int, input().split())
print(len([x for x in div(A) & div(B) if is_prime(x)]) + 1)

Submission status: Accepted

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

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

n=gcd(A,B)
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)

c=collections.Counter(a)
print(len(c.keys())+1)

Submission status: Accepted

Solution code:
import functools
import math

a,b = input().split()


def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

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

a = divisor(int(a))
b = divisor(int(b))
ans_list = list(set(a) & set(b))

# print(ans_list)
an = 1

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

print(an)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

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

    return arr

a, b = na()
c = gcd(a, b)
print(len(factorization(c))+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def factori(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())
G = gcd(A, B)

if G == 1:
    print(1)
else:
    print(len(factori(G)) + 1)

Submission status: Accepted

Solution code:
import fractions
import math
ans=1
a,b=map(int, input().split())
c=fractions.gcd(a,b)
d = []
for i in range(1, int(c**0.5)+1):
    if a % i == 0 and b % i == 0:
        d.append(i)
        if i != c // i :
            d.append(c//i)
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
for i in d:
    if is_prime(i):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import fractions
#A=int(input())
#A=list(map(int,(input().split())))
A,B=list(map(int,(input().split())))
C=fractions.gcd(A,B)
lis=[]
waru=2
while (C!=1 and waru<=C**0.5+10):
	
	if C%waru==0:
		lis.append(waru)
		while(C%waru==0):
			C/=waru
	waru+=1
if C!=1:lis.append(waru)
print(len(lis)+1)

Submission status: Accepted

Solution code:
str_list = input().split(' ')
int_list = [int(x) for x in str_list]
A, B = int_list[0], int_list[1]

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

    # divisors.sort()
    return divisors

a_div = make_divisors(A)
b_div = make_divisors(B)

cf = list( set(a_div) & set(b_div) )
cf.remove(1)
cf.sort()

count = 0

import numpy as np
cf = np.array(cf)

count = 0
while len(cf) > 0:
    count += 1
    if len(cf)==1:
        break
    x = int( cf[0] )
    cf = cf[np.where( cf%x!=0 )]
print(count+1)

Submission status: Accepted

Solution code:
from fractions import gcd
import math

def prime(x):
  if x==2:
    return True
  else:
      for j in range(2,math.ceil(math.sqrt(x))+1):
        if x%j==0:
          return False
          break
        else:
          pass
      else:
        return True
  
a,b = map(int,input().split())
ab = gcd(a,b)
lis = []
for i in range(1,math.ceil(math.sqrt(ab))+1):
  if ab%i==0:
    if prime(i) and i not in lis:
      lis.append(i)
    if prime(ab//i) and ab//i not in lis:
      lis.append(ab//i)
print(len(lis))

Submission status: Accepted

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

A,B=map(int,input().split())
A=make_divisors(A)
B=make_divisors(B)
C=list(set(A)&set(B))
C.sort()

for i in range(1,len(C)-1):
  a=C[i]
  for j in range(len(C)-1,i,-1):
    if C[j]%a==0: del C[j]
  if i+1>=len(C): break
print(len(C))

Submission status: Accepted

Solution code:
a,b = map(int,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
  
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))

print(len(s&t) + 1)

Submission status: Accepted

Solution code:
import fractions
a,b=map(int,input().split())
c=fractions.gcd(a,b)
#print(c)
l=[]
s=int(c**(1/2))+1
for i in range(1,s+1):
    if c%i==0:
        if i!=c//i:
            l.append(i)
            l.append(c//i)
        else:
            l.append(i)
l.sort()
l=l[::-1]
ans=1
#print(l)
for i in range(len(l)-1):
    for j in range(i+1,len(l)-1):
        if fractions.gcd(l[i],l[j])>=2:
            break
    else:
        ans+=1
print(ans)