Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
import math
import fractions
def factorization(n):
    arr = []
    temp = n
    if n!=1:
      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)
    else:
      return 0
print(factorization(fractions.gcd(A,B))+1)

Submission status: Accepted

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

a,b = inpl()

A = max(a,b)
B = min(a,b)

Alist =list()
i = 1
while i <= A/i :
    if A%i==0:
        Alist.append(i)
        Alist.append(A/i)
    i += 1
i=1
Blist =list()
while i <= B/i :
    if B%i==0:
        Blist.append(i)
        Blist.append(B/i)
    i += 1

Clist = list()
for i in range (len(Alist)):
    if Alist[i] in Blist:
        Clist.append(Alist[i])

Clist = list(set(Clist))
Clist.sort()

anslist = list()
for i in range(len(Clist)):
    if Clist[i]==1:
        anslist.append(Clist[i])
    elif len(anslist) == 1:
        anslist.append(Clist[i])
    elif len(anslist) >= 2:
        for j in range(1,len(anslist)):
            if Clist[i] % anslist[j] == 0:
                break
        else:
            anslist.append(Clist[i])

print(len(anslist))

Submission status: Accepted

Solution code:
import fractions
import heapq

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

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
import collections

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

gcd = gcd(a, b)


def prime_factorize(n):
    a = list()
    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


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

Submission status: Accepted

Solution code:
#D
import fractions

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

kouyaku = 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 a
import collections
c = collections.Counter(prime_factorize(kouyaku))
d =list(c.values())
print(len(d) +1)

Submission status: Accepted

Solution code:
import math
import fractions
import copy
def prime_factorize(n):
  d = {}
  f = 2
  while f * f <= n:
    if n % f == 0:
      n //= f
      if not f in d.keys():
        d[f] = 1
      else:
        d[f] += 1
    else:
      f += 1
  if n != 1:
    if not n in d.keys():
      d[n] = 1
    else:
      d[n] += 1 
  return d

a, b = map(int, input().split())
c = fractions.gcd(a,b)
d = prime_factorize(c)
print(len(d)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b=[int(i) for i in input().split()]
res=set()
x=gcd(a,b)
y=2
while y*y<=x:
  while x%y==0:
    res.add(y)
    x//=y
  y+=1
if x>1:
  res.add(x)
print(len(res)+1)

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

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


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

a_divsrs = set(make_divisors(a))
b_divsrs = set(make_divisors(b))

# print("a_divsrs:", *a_divsrs)
# print("b_divsrs:", *b_divsrs)

comm_divsrs = sorted(a_divsrs & b_divsrs)

# print("comm_divsrs:", *comm_divsrs)

ans = []
for i in range(len(comm_divsrs)):
    if not (comm_divsrs[i] % 2 == 0 and comm_divsrs[i] != 2):
        ans.append(comm_divsrs[i])

# print("ans:", *ans)

final_ans = ans[0:2]
# ct = 0

"""
    ans[i] に対して、すべての ans[j] (j: range[1:i]) が gcd(ans[i], ans[j]) == 1
    ならば final_ans に追加。ひとつでも違えば追加しない
"""
for i in range(2, len(ans)):
    is_ok = True
    for j in range(1, i):
        if gcd(ans[i], ans[j]) != 1:
            is_ok = False
            break
    if is_ok:
        final_ans.append(ans[i])

# print("final_ans:", *final_ans)
print(len(final_ans))
# print(ct)

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

A_divisors = make_divisors(A)
ans = 1
m = []
for d in A_divisors:
    if d == 1: continue
    if B%d==0:
        for mi in m:
            if d%mi == 0:
                break
        else:
            ans += 1
            m.append(d)
            continue
        
print(ans)

Submission status: Accepted

Solution code:
import math
A,B = map(int,input().split())
N = max(A,B)
prime = []

tA = A
tB = B
for i in range(2, math.ceil(N**0.5)+1):
    Aflag = False
    Bflag = False
    if tA%i==0:
        Aflag = True
        while tA%i==0:
            tA //= i
    if tB%i==0:
        Bflag = True
        while tB%i==0:
            tB //= i
    if Aflag == True and Bflag == True:
        prime.append(i)

if tA!=1 and tA == tB:
    prime.append(tA)

# print(prime)
print(len(prime)+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
A, B = map(int, input().split())
ls = defaultdict(int)
ans = 0
for i in range(1, max(int(A**0.5)+1, int(B**0.5)+1)):
  if A%i==0 and B%i==0:
    if ls[i]==0:
      ls[i]=1
      for n in range(2,int(i**0.5)+1):
        if i%n==0:
          break
      else:
        ans += 1
  if A%i==0:
    j = A//i
    if B%j!=0:
      continue
  elif B%i==0:
    j = B//i
    if A%j!=0:
      continue
  else:
    continue
  if ls[j]==0:
    ls[j] = 1
  else:
    continue
  for n in range(2,int(j**0.5)+1):
    if j%n==0:
      break
  else:
    ans += 1
print(ans)

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 gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

def coprime(a, b):
    return gcd(a, b) == 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 , B = map(int , input().split())
#A = 100000000000
#B = 50000000000
#print(make_divisors(A))

gcd_value = gcd(A , B)
cd = []
div = make_divisors(gcd_value)

for i in range(len(div)):
    if A % div[i] == 0 and B % div[i] == 0 and is_prime(div[i]):
        cd.append(div[i])
print(len(cd) + 1)

Submission status: Accepted

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

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

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

    return arr
lis = list(factorization(A))
counter = 0
for i in range(len(lis)):
  jud = B/lis[i][0]
  if jud.is_integer():
    counter += 1
if A == 1 or B == 1:
  print(1)
else:
  print(counter+1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
C = []
D = []
def prime_factor(n):
  E = []
  for i in range(2, int(n ** 0.5) + 1):
    while n % i == 0:
      E.append(i)
      n = n // i
  if n != 1:
    E.append(n)
  return E
C = prime_factor(A)
D = prime_factor(B)
f = set(C) & set(D)
print(len(f)+1)

Submission status: Accepted

Solution code:
import fractions as fra
import math
a,b = map(int,input().split())
n = fra.gcd(a,b)
tmp = int(math.sqrt(n)) + 1
l = [1]
ans = 0
for i in range(2,tmp):
  while n % i == 0:
    n //= i
    if i not in l:
      l.append(i)
      ans += 1
if n not in l:
  ans += 1
  
print(ans+1)

Submission status: Accepted

Solution code:
aa, bb = map(int, input().split())
A = max(aa, bb)
B = min(aa, bb)


def get_max(a, b):
    while True:
        c = a % b
        if c == 0:
            return b
        a = b
        b = c


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


B = get_max(A, B)
factors = factorize(B)

if len(factors) == 0:
    print(1)
else:
    count = 1
    for i in range(0, len(factors) - 1):
        if factors[i] != factors[i + 1]:
            count += 1
    print(count + 1)

Submission status: Accepted

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

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

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

    if not arr:
        arr.add(n)

    return arr

if a == b == 1:
    print(1)
else:
    fa = factorization(a)
    fb = factorization(b)
    res = 1
    for n in fa:
        if n in fb:
            res += 1
    print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

def divisor(n):
    i = 1
    l = list()
    while i * i <= n:
        if n % i == 0:
            l.append(i)
            l.append(n // i)
        i += 1
    l = list(set(l))
    return l

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

ans = list()
a = divisor(A)
b = divisor(B)
d = a + b
l = list()
for i in set(d):
    if d.count(i) > 1:
        l.append(i)

if len(l) > 1:
    ans.append(l[0])
    for i in range(1, len(l)):
        if is_prime(l[i]):
            ans.append(l[i])
else:
    ans = l

# output
print(len(ans))

Submission status: Accepted

Solution code:
# 素因数分解
def fac(n):
    arr = [1]
    temp = n 
    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 len(arr) == 1:
        arr.append(n)
    return set(arr)


A, B  = map(int, input().split())
ans =  fac(A) & fac(B)
print(len(ans))

Submission status: Accepted

Solution code:
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, cnt])

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

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

    return arr
  
A, B = input().split()
 
A = int(A)
B = int(B)

gcd_num =gcd(A,B)

gcd_list = factorization(gcd_num)

t = len(gcd_list)
if gcd_list == [[1, 1]]:
  print(t)
else:
  print(t+1)

Submission status: Accepted

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

A,B = list(map(int,input().split()))
GCD = gcd(A,B)
CD = []
for i in range(1,int(GCD**(0.5))+1):
    if GCD % i == 0:
        CD.append(i)
        if not i == GCD//i:
            CD.append(GCD//i)
CD.sort()
ans = 1
tmp_idx = 0
CD.pop(0)
CD_old = CD[:]
while (len(CD_old)>0):
    tmp = CD_old.pop(0)
    CD_new = []
    for i in range(len(CD_old)):
        if not CD_old[i] % tmp == 0:
            CD_new.append(CD_old[i])
    ans += 1
    CD_old = CD_new
print(ans)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline-------------------------------------------
    a,b = map(int,input().split())
    d = gcd(a,b)
    p = int(math.sqrt(d))+1
    div = []
    for i in range(1,p):
        if d%i==0:
            if d//i != i:
                div.append(i)
                div.append(d//i)
            else:
                div.append(i)
    div.sort()
    n = len(div)
    sgn = [1]*(n)
    if len(sgn) != 1:
        for i in range(1,len(sgn)):
            if sgn[i] == 1:
                for j in range(i+1,n):
                    if div[j]%div[i] == 0:
                        sgn[j] = 0
        res = []
        for i in range(n):
            if sgn[i] == 1:
                res.append(div[i])
        print(len(res))
    else:
        print(1)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import math

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

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

    return sorted(divisors)[::-1]

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

gcd = get_gcd(a, b)
list = get_divisors(gcd)

#print(list)

count = 0
length = len(list)
for i in range(length):
    is_ok = True
  
    for j in range(i+1, length):
        if (get_gcd(list[i], list[j]) != 1):
            is_ok = False
            break
    
    if is_ok:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import fractions
# fractions.gcd(x,y)

def div(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)

    return divisors
a,b=map(int,input().split())
x=div(a)
y=div(b)
#z=x&y
z=list(x&y)
z.sort()
t=len(z)
ans=1
for i in range(1,t):
    f=1
    for j in range(1,i):
        if (z[i]%z[j]==0):
            f=0
            break
    if f:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math

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

def func(n):
    num=1
    for i in range(2,int(math.sqrt(n) + 1e-9) +3):
        if n%i==0 and n!=i:
            num=0
            break
        else:
            continue
    return num

p=min(A,B)
q=max(A,B)

ans=0
check=[]
for i in range(1, int(math.sqrt(p)+ 1e-9)+3):
    if p%i==0:
        if i not in check:
            check.append(i)
        if p//i not in check:
            check.append(p//i)

for i in check:
    if q%i==0:
        ans+=func(i)

print(ans)

Submission status: Accepted

Solution code:
import math

def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
  
  # nの平方根まで計算する
    m = math.floor(math.sqrt(n)) + 1
    for p in range(3, m, 2):
        if n % p == 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

def main():
    A, B = [int(i) for i in input().split()]
    count = 0
    a = []
    prime = []
    if A > B:
        temp = A
        A = B
        B = temp
    a = make_divisors(A)
    
    for i in a:
        if isPrime(i) == True:
            prime.append(i)
    for i in prime:
        if B % i == 0:
            count += 1

    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

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

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

def main():
  a, b = sorted(na())
  x = divi(a)
  cnt = 1
  for bb in divi(b):
    if bb in x and isprime(bb):
      cnt += 1
  print(cnt)
main()

Submission status: Accepted

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

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

g = gcd(A,B)

count = 0
l = []

while g%2 == 0:
    l.append(2)
    g //= 2
i = 3
while i**2 <= g:
    if g%i == 0:
        l.append(i)
        g //= i
    else:
        i += 2
if g != 1:
    l.append(g)

print(len(set(l))+1)

Submission status: Accepted

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

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 isPrime(n):
  if n <= 2:
    return True
  m = int((n**0.5)//1 + 1)
  for p in range(2, m):
      if n % p == 0:
        return False
  return True
    
a,b = map(int,input().split())
gcd = gcd(a,b)
yks = make_divisors(gcd)
ans = 0
for i in yks:
  if isPrime(i):
    ans +=1
print(ans)

Submission status: Accepted

Solution code:
import math
A, B = map(int,input().split())
A_cf = []
B_cf = []
for i in range(1,int(A**0.5)+1):
    if A % i == 0:
        A_cf.append(i)
        if i != A // i:
            A_cf.append(A//i)
for i in range(1,int(B**0.5)+1):
    if B % i == 0:
        B_cf.append(i)
        if i != B // i:
            B_cf.append(B//i)
DA = dict()
for i in range(len(A_cf)):
    DA[A_cf[i]] = False

for i in range(len(B_cf)):
    if B_cf[i] in DA:
        DA[B_cf[i]] = True
cf = []
for i in range(len(A_cf)):
    if DA[A_cf[i]]:
        if A_cf[i] % 2 == 0 and A_cf[i] != 2:
            continue
        cf.append(A_cf[i])
prime_num = []
cf.sort()

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
for i in range(len(cf)):
    if isPrime(cf[i]):
        prime_num.append(cf[i])

ans = len(prime_num) + 1
print(ans)

Submission status: Accepted

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


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

    if flag:
        return n


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

    divisors.sort()
    return divisors


def main():
    a, b = map(int, input().split())
    coms = make_divisors(fractions.gcd(a, b))
    ans = [is_prime(i) for i in coms]
    ans2 = [a for a in ans if a is not None]
    print(len(ans2))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
import heapq
import itertools


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


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

cd = []
max_cd = fractions.gcd(A, B)

if max_cd == 1:
    cd.append(1)
else:
    heapq.heappush(cd, 1)

    f = [k[0] for k in factorize(max_cd)]
    for v in f:
        heapq.heappush(cd, v)

l = []

for i in range(0, len(cd)):
    c = heapq.heappop(cd)
    if not l:
        l.append(c)
    else:
        join = True
        for j in range(0, len(l)):
            k = l[j]
            if fractions.gcd(c, k) != 1:
                join = False
                break
        if join:
            l.append(c)

print(len(l))

Submission status: Accepted

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

import fractions

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 a

PF = prime_factorize(GCD)

PF = set(PF)

res = len(PF) + 1

print(res)

Submission status: Accepted

Solution code:
import math

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

A_divs = make_divisors(A)
B_divs = make_divisors(B)

A_divs_len = len(B_divs)
B_divs_len = len(B_divs)
AB_divs = []

if A_divs_len >= B_divs_len:
    for v in B_divs:
        if v in A_divs:
            AB_divs.append(v)
        else:
            continue
else:
    for w in A_divs:
        if w in B_divs:
            AB_divs.append(w)

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

primes = []

for v in AB_divs:
    if is_prime(v):
        primes.append(v)

primes.insert(0, 1)
print(len(primes))

Submission status: Accepted

Solution code:
aa,bb = map(int,input().split())
n = min(aa,bb)
b = max(aa,bb)
ans = 1
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==[] and n != 1:
         arr.append(n)

for j in range(len(arr)):
         if b % arr[j] == 0:
                  ans += 1
print (ans)

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)
k=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)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors
m=make_divisors(k)
x=len(m)
n=len(m)

for _ in range(n-1):
  for i in range(1,len(m)):
    if gcd(m[i],m[0])!=1:
      x-=1
      m.pop(0)
      break
    if i+1 == len(m):
      m.pop(0)
      break
print(x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np 
import math

#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, cnt])

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


    return arr

a,b = list(map(int,input().split()))
x = gcd(a,b)
# print(gcd)
# print(factorization(gcd))
print(len(factorization(x))+1)

Submission status: Accepted

Solution code:
AB = input().split(' ')
A = int(AB[0])
B = int(AB[1])
'''
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
                cf.append(i)
    return cf
 
def check_cf(x1,x2):
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            return False
    return True
candidate = cf(A,B)
'''
'''
decided_list = [candidate[0]]
 
for i in range(1,len(candidate)):
    flag = True
    for s in range(2,candidate[i]):
        if candidate[i]%s == 0:
            flag = False
            break
    if flag:
        decided_list.append(candidate[i])
'''
#print(candidate)
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 gcd(num1: int, num2: int) -> int:
    if num2 == 0:
        return num1
    else:
        return gcd(num2,num1%num2)
max_gcd = gcd(A,B)
result = factorization(max_gcd)
#print(result)
if len(result) == 1 and result[0][0] == 1:
    print(1)
else:
    print(len(result)+1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
A,B = list(map(int, readline().split()))

def factorization(n):
    arr = [[1,1]]
    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 gdc(x,y):
    if y == 0:
        return x
    return gdc(y, x % y)

g = gdc(B,A)
res = factorization(g)
# print(g,res)
print(len(res))

Submission status: Accepted

Solution code:
import math
import fractions

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

# 約数リスト
l = []
x = fractions.gcd(a,b)
for i in range(1, x):
    if i ** 2 > x : break
    if x % i == 0:
        l.append(i)
        if i != x // i:
            l.append(x//i)

if l == []:
    l.append(1)
#print(l)

def isprime(x):
    if x <= 3:
        return True
    elif x % 2 == 0:
        return False
    else:
        i = 3
        while i <= math.sqrt(x):
            if x % i == 0:
                return False
            i = i +2
        return True

ans = []
for i in l:
    if isprime(i):
        ans.append(i)

print(len(ans))

Submission status: Accepted

Solution code:
import math


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

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True


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

    # divisors.sort()
    return divisors

a=set(make_divisors(a))
b=set(make_divisors(b))

cout=0
for i in a&b:
  if isPrime(i) == True:
    cout+=1

print(cout)

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 a
prime_num = prime_factorize(gcd)
print(len(set(prime_num))+1)

Submission status: Accepted

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

xx = []
for n in [a, b]:
    x = []
    if n == 1:
        xx.append([n])
        continue

    x.append(1)
    while n % 2 == 0:
        x.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            x.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        x.append(n)
    xx.append(x)

print(len(set(xx[0]) & set(xx[1])))

Submission status: Accepted

Solution code:
def get_gcd(x, y):
    if x < y:
        y, x = x, y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x

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())
gcd = get_gcd(a, b)
common_divisors = prime_factorize(gcd)
print(len(set(common_divisors)) + 1)