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:
# coding: utf-8
# Your code here!
def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    
    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
    
    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())
    c=gcd(a,b)
    cnt=0
    d=divisor(c)
    for i in d:
        if is_prime(i):
            cnt+=1
    print(cnt)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
def main():

    A, B = map(int, input().split())
    C = min(A, B)
    p = set()
    p.add(1)
    for i in range(2, int(math.sqrt(C))+1):
        if C % i == 0:
            if A % i == 0 and B % i == 0:
                if isprime(i): p.add(i)
            j = C // i
            if A % j == 0 and B % j == 0:
                if isprime(j): p.add(j)

    if isprime(C) and A%C == 0 and B%C == 0:
        p.add(C)

    return len(p)

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

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import fractions

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

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

print(len(set(factorize(kouyakusu)))+1)

Submission status: Accepted

Solution code:

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

N= input().split() 
A=divisor(int(N[0]))

B=divisor(int(N[1]))
count=1
for i in A:
    if (i in B):
        if is_prime(i):
            count+=1

print(count)

Submission status: Accepted

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

ans=1
ans+=len(set(prime_factorize(gcd_ab)))
print(ans)

Submission status: Accepted

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


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


aa = prime_decomposition(a)
bb = prime_decomposition(b)

print(len(aa & bb))

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x<y:
        x,y = y,x
    while y>0:
        x,y = y,x%y
    return x
INFTY = 10**6
P = [1 for i in range(INFTY+1)]
P[0] = 0
P[1] = 0
for i in range(2,int((INFTY+1)**0.5)+1):
    for j in range(i*i,INFTY+1,i):
        P[j] = 0
Q = []
for i in range(INFTY):
    if P[i]==1:
        Q.append(i)
A,B = map(int,input().split())
x = gcd(A,B)
cnt = 1
for y in Q:
    if x%y==0:
        cnt += 1
        while x%y==0:
            x = x//y
if x>1:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)
import math
a,b = map(int,input().split())
x = gcd(a,b)
c= x
ans = 1
for i in range(2,int(math.sqrt(x))+1):
    if(c%i==0):
        ans+=1
    while(c%i==0):
        c=c//i
        
if(c>1):
    ans+=1
print(ans)

Submission status: Accepted

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

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

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

    return arr

a, b = list(map(int, input().split()))
fa = set(factorize(a))
fb = set(factorize(b))
if a == 1 and b == 1:
    print(1)
else:
    print(len(fa & fb) + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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())
a_list = prime_factorize(a)
a_set = set(a_list)
b_list = prime_factorize(b)
b_set = set(b_list)

print(len(a_set & b_set)+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

#最大公約数
def my_gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
    
gcd_n = my_gcd(max(A,B),min(A,B))

if A==1 or B==1:
    print(1)
else:
    print(len(factorization(gcd_n))+1)

Submission status: Accepted

Solution code:
import fractions
import math
A, B = map(int, input().split())
div_gcd = set()
gcd = fractions.gcd(A, B)
for i in range(1, math.ceil(math.sqrt(gcd))):
    if (gcd / i) % 1 == 0:
        div_gcd.add(i)
        div_gcd.add(gcd / i)
div_gcd.discard(1)
divlist = list(div_gcd)
divlist = sorted(divlist)
ansset = set()
for k in divlist:
    if len(ansset) == 0:
        ansset.add(k)
    else:
        flag = 1
        for j in ansset:
            if (k / j) % 1 == 0:
                flag = 0
                break
        if flag == 1:
            ansset.add(k)

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

Submission status: Accepted

Solution code:
from math import sqrt


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

    return True


def f(x):
    st = set()
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            st.add(i)
            st.add(x // i)

    return st


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

a_set = f(a)
b_set = f(b)

ans = 0
for e in a_set:
    if is_prime(e) or e == 1:
        if e in b_set:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


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

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


    
def main(): 
    gcdAB = gcd(A, B)
    C = prime_decomposition(gcdAB)
    C.append(1)
    C = set(C)
        
    print(len(C))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b = (int(i) for i in input().split())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
def is_prime(n):
  for p in range(2, n):
    if n % p == 0:
      return False
  return True

cnt = 0

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
  
list = prime_factorize(gcd(a,b))

print(len(set(list))+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)
  return divisors

def make_cd(x, y):
  div1=make_divisors(x)
  div2=make_divisors(y)
  cd=[]
  for i in div1:
    for j in div2:
      if i==j:
        cd.append(i)
        break
  cd.sort()
  return cd

A, B=map(int, input().split())
if A<B:
  A,B=B,A
cd=make_cd(A, B)
ok=[True for _ in range(len(cd))]
for i in range(1, len(cd)):
  if not ok[i]:
    continue
  for j in range(i+1, len(cd)):
    if cd[j]%cd[i]==0:
      ok[j]=False
print(sum([1 if ok[i] else 0 for i in range(len(cd))]))

Submission status: Accepted

Solution code:
def main():
    A, B = (int(i) for i in input().split())
    from fractions import gcd
    g = gcd(A,B)
    divs = []
    for i in range(1,int(g**0.5)+1):
        if g % i == 0:
            divs.append(i)
            if i != g//i:
                divs.append(g//i)
    divs.sort()
    ans = {1}
    n = len(divs)
    for i in range(n):
        cur = divs[i]
        for j in ans:
            if gcd(cur,j) != 1:
                break
        else:
            ans.add(cur)
    print(len(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

pfa = {}
for i in range(2, int(A**0.5) + 1):
    while A % i == 0:
        pfa[i] = pfa.get(i, 0) + 1
        A //= i
if A > 1:
    pfa[A] = pfa.get(A, 0) + 1

pfb = {}
for i in range(2, int(B**0.5) + 1):
    while B % i == 0:
        pfb[i] = pfb.get(i, 0) + 1
        B //= i
if B > 1:
    pfb[B] = pfb.get(B, 0) + 1

s = set(pfa.keys()) & set(pfb.keys())
print(len(s) + 1)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

def acinput():
    return list(map(int, input().split(" ")))


A, B = acinput()

x=factorization(gcd(A,B))
if x[0][0]==1:
    n=1
else:
    n=len(x)+1

if n==1:
    print(1)
else:
    print(n)

Submission status: Accepted

Solution code:
import math

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

tmpA = max(a, b)
tmpB = min(a, b)

while tmpB != 0:
    newB = tmpA % tmpB
    tmpA = tmpB
    tmpB = newB

tmp = tmpA
res = 1

for i in range(2, int(math.sqrt(tmp)) + 1):
    if tmp % i == 0:
        res += 1
        tmp //= i
    else:
        continue

    while tmp % i == 0:
        tmp = tmp//i


if tmp != 1:
    res += 1

print(res)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
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_list = list(collections.Counter(prime_factorize(A)).keys())

B_list = list(collections.Counter(prime_factorize(B)).keys())

A_B_and = set(A_list) & set(B_list)
print(len(A_B_and) + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]

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

A,B = [int(x) for x in input().split()]
dA = set(prime_decomposition(A))
dB = set(prime_decomposition(B))

cm = dA.intersection(dB)
cm.add(1)

print(len(cm))

Submission status: Accepted

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

n=gcd(A,B)
K=int(n**0.5)+2

s=set()
s.add(1)

for i in range(2,K):
		while n%i==0:
			s.add(i)
			n/=i
else:
	s.add(n)

print len(s)

Submission status: Accepted

Solution code:
import numpy as np
def is_prime(n):
    if n == 1: return True

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

    return True

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

    # divisors.sort()                                                                                  
    return divisors

l = map(int, raw_input().split())
A = l[0]
B = l[1]

d_a = make_divisors(A)
d_b = make_divisors(B)

cd = set(d_a) & set(d_b)

#print cd                                                                                              

sum = 0
for item in cd:
    if is_prime(item) == True:
        sum = sum + 1

print sum

Submission status: Accepted

Solution code:
from fractions import gcd
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 = map(int,input().split())
g=gcd(A,B)
c = collections.Counter(prime_factorize(g))
print(len(c.keys())+1)

Submission status: Accepted

Solution code:
#D
from fractions import gcd
#from math import gcd
import collections
a, b = map(int,input().split())
tmp = 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

if tmp == 1:
    l = 1
    ans = 1
else:
    l = prime_factorize(tmp) + [1]
    clist = collections.Counter(l)
    ans = len(clist.keys())
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

def make_divisors_without_own(n):
    r = make_divisors(n)
    r.remove(1)
    r.remove(n)
    return r

a, b = map(int, input().split())
aa = set(make_divisors(a))
bb = set(make_divisors(b))
u = aa & bb
u = u - set([1])
#print(u)
u = list(u)
u.sort()
res = 0
for i in range(len(u)):
    if make_divisors_without_own(u[i]) == []:
        res += 1
print(res + 1)

Submission status: Accepted

Solution code:
from sys import stdin
import fractions

A, B = [int(x) for x in stdin.readline().rstrip().split()]
gcd = fractions.gcd(A, B)
C = []
y = 1
while y ** 2 <= gcd:
    if gcd % y == 0:
        if y >= 2:
            C.append(y)
        if y ** 2 != gcd:
            C.append(gcd // y)
    y += 1

ans = 1
g = 1
C.sort()
for c in C:
    while gcd % c == 0:
        gcd //= c
        if g != c:
            ans += 1
        g = c

print(ans)

Submission status: Accepted

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


a, b = list(map(int, input().split()))
d = gcd(a, b)
if d == 1:
    print(1)
    quit()
li = []
while True:
    for i in range(2, int(math.sqrt(d)) + 1):
        if d % i == 0:
            if not i in li:
                li.append(i)
                d = d // i
                break
            else:
                d = d // i
                break
    else:
        if d != 1:
            li.append(d)
            break

print(len(set(li)) + 1)

Submission status: Accepted

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

def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if a==b:
    return a
  else:
    if a%b==0:
      return b
    return gcd(b,a%b)
  
v=gcd(A,B)

def bunnkai(N):
  lst=[1]
  tmp=N
  for i in range(2,int(math.sqrt(N)+1)):
    if tmp%i==0:
      while tmp%i==0:
        tmp//=i
      lst.append(i)
  if tmp!=1:
    lst.append(tmp)
  if lst==[]:
    lst.append(N)
  return lst

print(len(bunnkai(v)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
A, B = inpl()

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P

P = primes(10**6)

ans = 1

ext = []

ais = True
bis = True

S = min(A, B)
for p in P:
    if p > min(A, B):
        break
    ans += int(A%p == B%p == 0)
    while A%p == 0:
        A //= p
    while B%p == 0:
        B //= p
else:
    if A > 1:
        ans += int(B%A == 0)
    elif B > 1:
        ans += int(A%B == 0)

print(ans)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
if A == B == 1:
    print(1)
    exit(0)


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 set([val[0] for val in arr])

print(len(factorization(A) & factorization(B))+1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

num_gcd = gcd(A,B)

ans = [1]
number = num_gcd

if number%2==0:
  ans.append(2)
  number = number//2
  while number%2==0:
    number = number//2 

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

print(len(ans))

Submission status: Accepted

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

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

base = gcd(a, b)

yakusu = make_divisors(base)
rest = copy.deepcopy(yakusu)

count = 0
ans = []
for v in yakusu:
    if v == 1:
        ans.append(1)
        continue
    if rest == []:
        break
    new_rest = []
    for r in rest:
        if r == 1:
            continue
        if r == v:
            ans.append(r)
            continue
        if r % v != 0:
            new_rest.append(r)
    rest = new_rest

print(len(set(ans)))

Submission status: Accepted

Solution code:
import math
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
    table = list(set(table))
    return table


a_div = divisor(a)
b_div = divisor(b)
a_b_div = list(set(a_div) & set(b_div))

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

ans = 0
for i in a_b_div:
    if is_prime(i) == True:
        ans += 1
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

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 = map(int,input().split())
minnum,maxnum = sorted([A,B])
div_l = factorization(gcd(minnum,maxnum))

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

Submission status: Accepted

Solution code:
import fractions
import math

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

kosuu = 1  # 1

if saidai % 2 == 0:
    kosuu += 1

while saidai % 2 == 0:
    saidai = saidai // 2

# sqrt = int(math.sqrt(gcd))
# for i in range(3, sqrt+1+1, 2):
#     if saidai <= 1:
#         break

#     if saidai % i == 0:
#         kosuu += 1

#     while saidai % i == 0:
#         saidai = saidai // i

i = 3
while True:
    if saidai <= 1:
        break

    if i > math.sqrt(saidai):
        break

    if saidai % i == 0:
        kosuu += 1

    while saidai % i == 0:
        saidai = saidai // i

    i += 2

if saidai != 1:
    kosuu += 1

print(kosuu)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from copy import deepcopy
#import heapq
#import math
#import string
from fractions import gcd

setrecursionlimit(10**6)
input=stdin.readline

def factorization(num):
    ans=set()
    tmp=num
    for i in range(2,int(num**0.5)+1):
        while tmp%i==0:
            ans.add(i)
            tmp//=i
    if ans==[]:
        ans.add(num)
    elif tmp!=1:
        ans.add(tmp)
    return ans

a,b=map(int,input().split())
pa,pb=factorization(a),factorization(b)
pa.add(1);pb.add(1)

print(len(pa&pb))

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()
    new_divisors = []
    for i, _divisors in enumerate(divisors[::-1]):
        for _remain_divisors in divisors[::-1][i+1:][:-1]:
            if _divisors % _remain_divisors == 0:
                break
        else:
            new_divisors.append(_divisors)
    return new_divisors

    if n == 1:
        return([1])
    divisors = [1, n]
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            if i != n // i:
                div_append = [i, n // i]
            else:
                div_append = [i]
            for _divisors in divisors[1:]:
                if len(div_append) == 0:
                    break
                div_append = [_div_append for _div_append in div_append if _div_append % _divisors != 0]
            else:
                divisors += div_append
    return divisors

def main():
    a, b = map(int, open(0).read().split())

    div_a = make_divisors(a)
    div_b = make_divisors(b)

    cnt = 0
    for _div_a in div_a:
        if _div_a in div_b:
            cnt += 1

    ans = cnt
    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
a,b = map(int,input().split())
n = int(max(a,b)**(0.5))
m = min(a,b)
ans = 1
for i in range(2,min(m,n)+1):
    if a%i == 0 and b%i == 0:
        while a % i == 0 and b % i == 0:
            a //= i
            b //= i
        ans += 1
if gcd(a,b) != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
A, B = list(int(el) for el in input().split(' '))


if (A==1) or (B==1): 
  print(1) 
  is_print=False
else:
  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

  fact_a = factorization(A)
  fact_b = factorization(B)

  set_a = set()
  set_b = set()

  set_a.add(1)
  set_b.add(1)

  for fa, _ in fact_a: set_a.add(fa)
  for fb, _ in fact_b: set_b.add(fb)


  print(len(set_a & set_b))

Submission status: Accepted

Solution code:

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

while B:
    A, B = B, A % B
n = A



if n == 1:
    print(1)
else:
    arr = []
    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)

    print(len(arr)+1)

Submission status: Accepted

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


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

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


divs = divisor(n)
ans = 0

for d in divs:
    ans += is_prime(d)


print(ans+1)

Submission status: Accepted

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

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

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)