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=[int(j) for j in 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
la=set(make_divisors(a))
lb=set(make_divisors(b))
l=list(la&lb)
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

ans=0
ll=set([1])
l.sort()
for i in l:
    if i==1:
        continue
    if set(make_divisors(i))&ll=={1}:
        ll.add(i)
print(len(ll))

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
def gcd(a,b):
    if b==0:
        return a 
    return gcd(b,a%b)
g=gcd(a,b)

from math import sqrt as S
#print(gcd(a,b))
def get_div(x):
    if x==1:
        return [1]
    div=[1,x]
    for i in range(2,int(S(x))+1):
        if x%i==0:
            div.append(i)
            if i!=x//i:
                div.append(x//i)
    return div 
div=get_div(g)
p=10**6+5 
def sieve():
    l=[1]*p 
    i=2 
    while i*i<=p:
        if l[i]:
            for j in range(i*i,p,i):
                l[j]=0 
        i+=1 
    l[0]=0 
    return l 
isp=sieve()
cnt=0 
def pr(n):
    if n<=1:
        return 0 
    return all(n%i for i in range(2,int(S(n))+1))
for i in div:
    if i<=10**6:
        if isp[i]:
            cnt+=1 
    else:
        if pr(i):
            cnt+=1 
print(cnt)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, 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()
    return divisors


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


a, b = map(int, input().split())
g = gcd(a, b)
kouyakusu = make_divisors(g)
ans = 1
for i in kouyakusu:
    if is_prime(i):
        ans += 1
print(ans)

Submission status: Accepted

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

def Prime_factorization(n):
    ans = []
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp%i == 0:
            count = 0
            while tmp%i == 0:
                count += 1
                tmp //= i
            ans.append([i,count])
    if tmp != 1:
        ans.append([tmp, 1])
    return ans
print(len(Prime_factorization(fractions.gcd(A,B)))+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)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr
if __name__ == "__main__":
    A,B = map(int,input().split())
    d = gcd(A,B)
    if d == 1:
        print(1)
    else:
        D = factorization(d)
        print(len(D)+1)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
#n = int(input())
#an = list(map(int, input().split()))

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

#print(gcd)

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

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

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

    return arr
if gcd == 1:
  print(1)
else:
  primes = factorization(gcd)
  print(len(primes)+1)

Submission status: Accepted

Solution code:
import fractions
a, b = map(int, input().split())
 
c =fractions.gcd(a,b)
c2 = c
F = []
while c2%2==0:
    c2 //= 2
if c2<c:
    F.append(2)
f = 3
while f*f<c2:
    while c2 %f ==0:
        c2//=f 
        if F:
            if F[-1]<f:
                F.append(f)
        else:
            F.append(f)
    f += 2
if c2>1:
    F.append(f)
print(len(F)+1)

Submission status: Accepted

Solution code:
import fractions as fr
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
p = fr.gcd(A,B)

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

Submission status: Accepted

Solution code:
import math

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)

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

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

    arr.append(1)
    return arr

A_ = set(factorization(A))
B_ = set(factorization(B))

print(len(A_ & B_))

Submission status: Accepted

Solution code:
import fractions
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

v=fractions.gcd(a, b)
ans=prime_factorize(v)
print(len(set(ans))+1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
a = set()
b = set()
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
"""
i = 2
temp = A + 0
while i * i <= temp:
  if A <= 1:
    break
  while A % i == 0:
    a.add(i)
    A //= i
  i += 1
i = 2
temp = B + 0
while i * i <= temp:
  if B <= 1:
    break
  while B % i == 0:
    b.add(i)
    B //= i
  i += 1
"""
a = set([i[0] for i in factorization(A)])
b = set([i[0] for i in factorization(B)])
inter = a.intersection(b)
if A == 1 and B == 1:
  print(1)
else:
  print(len(inter) + 1)

Submission status: Accepted

Solution code:
import sys
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def gcd(a,b):
    if a==0:
        return b
    else:
        return gcd(b%a,a)
def all_factors(n):
    small, large = [], []
    for i in range(1, int(n**0.5) + 1, 2 if n & 1 else 1):
        if not n % i:
            small.append(i)
            large.append(n // i)
    if small[-1] == large[-1]:
        large.pop()
    large.reverse()
    small.extend(large)
    return small
def is_prime(n):
    if n < 5 or n & 1 == 0 or n % 3 == 0:
        return 2 <= n <= 3
    s = ((n - 1) & (1 - n)).bit_length() - 1
    d = n >> s
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        p = pow(a, d, n)
        if p == 1 or p == n - 1 or a % n == 0:
            continue
        for _ in range(s):
            p = (p * p) % n
            if p == n - 1:
                break
        else:
            return False
    return True

a,b=get_ints()
g=gcd(a,b)
lst=all_factors(g)
count=1
for i in lst:
    if is_prime(i):
        count+=1
print(count)

Submission status: Accepted

Solution code:
from fractions import gcd

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

a, b = nm()

def prime_factorize(n):
    a = set()
    a.add(1)
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a



ps = prime_factorize(gcd(a,b))

print(len(ps))

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())
set_a=set(prime_factorize(a))
set_b=set(prime_factorize(b))
l=len(set_a & set_b)
print(l+1)

Submission status: Accepted

Solution code:
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

print(len(set(prime_factorize(A)) & set(prime_factorize(B)))+1)

Submission status: Accepted

Solution code:
def gcd(a,b):
	x,y = max(a,b), min(a,b)
	while x % y > 0:
		tmp = x % y
		x = y
		y = tmp
	return y

A,B = map(int,input().split())
G = gcd(A,B)
prime = [i % 2 == 1 for i in range(10**6 + 1)]
prime[1] = False
prime[2] = True
p = 3
while p <= 10**6:
	if prime[p]:
		for i in range(2*p, 10**6+1, p):
			prime[i] = False
	p += 2
P = [i for i in range(10**6+1) if prime[i]]

ans = 1
for p in P:
	if G % p != 0:
		continue
	ans += 1
	while G % p == 0:
		G = G // p
	if G == 1:
		break
if G > 1:
	ans += 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
A,B=map(int,input().split())
G=gcd(A,B)
a=1
for i in range(2,10**6+1):
    t=0
    while 1:
        if G%i==0:
            G//=i
            t+=1
        else:
            break
    if t:
        a+=1
if G>10**6:
    a+=1
print(a)

Submission status: Accepted

Solution code:
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

# 約数
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 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)
divs = make_divisors(gcd)
# ps = getprime(gcd)
if len(divs)==1:
    print(1)
else:
    print(len(factorization(gcd))+1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

    return arr

a, b = list(map(int, input().split()))
fct = factorization(gcd(a, b))
if not (len(fct) == 1 and fct[0][0] == 1):
    fct.append([1, 1])

#print(fct)
print(len(fct))

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

p=make_divisors(a)
q=make_divisors(b)
x=set(p)&set(q)
x=list(x)
cnt=0
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
for i in range(len(x)):
	if is_prime(x[i])==True:
		cnt+=1
print(cnt+1)

Submission status: Accepted

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

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 solve(A: int, B: int):
    A = set(prime_factorize(A))
    B = set(prime_factorize(B))

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


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a,b=list(map(int, input().split()))
def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

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

c = md(gcd(a,b))
c.sort()
if len(c)== 1:
    count = 1
else:
    count = 1
    d = c[0]
    for i in c[1:]:
        if coprime(d, i):
            d = d*i
            count += 1
        else:
            continue

print(count)

Submission status: Accepted

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

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

ans = 1

for i in range(2, 2*10**6):
    if g%i == 0:
        ans += 1
        while g%i == 0:
            g //= i

if not g == 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import defaultdict
def getlist():
	return list(map(int, input().split()))

L = [1 for i in range(1000001)]
L[0] = 0
L[1] = 0
plist = []
for i in range(1000001):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 1000000:
				L[i * c] = 0
				c += 1
			else:
				break

#処理
A, B = getlist()
G = gcd(A, B)
D = defaultdict(int)
for i in plist:
	while True:
		if G % i == 0:
			D[i] += 1
			G = G // i
		else:
			break
if G != 1:
	D[G] += 1

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

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
s,t=[1],[1]
for i in range(2,int(a**0.5)+1):
    if a%i==0:
        s.append(i)
        while a%i==0:
            a//=i
    if a==1:
        break
if a!=1:
    s.append(a)
for i in range(2,int(b**0.5)+1):
    if b%i==0:
        t.append(i)
        while b%i==0:
            b//=i
    if b==1:
        break
if b!=1:
    t.append(b)
print(len(set(s)&set(t)))

Submission status: Accepted

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

input = sys.stdin.readline

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

n = 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

frl = factorization(n)
if frl[0][0]==1:
	ans = 1
else:
	ans = len(frl)+1
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def solve(n):
    prime = 1
    m = n
    for i in range(2,int(sqrt(n))+1):
        pri = False
        while m%i==0:
            m//=i
            pri = True
        if pri:
            prime += 1
    if m!=1:
        prime+=1
    return prime
def main():
    A,B = MI()
    G = gcd(A,B)
    ans = solve(G)
    print(ans)
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 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 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

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

Submission status: Accepted

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

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 solve(A: int, B: int):
    A_primes = set(prime_factorize(A))
    B_primes = set(prime_factorize(B))
    print(len(A_primes & B_primes) + 1)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

a,b=map(int,input().split())
x=gcd(a,b)
l=factorization(x)
ans=1
ans+=len(l)
if x==1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math
N,M = [int(x) for x in input().split()]
e = {}
a = {}
for j in range(2,int(math.sqrt(M)) +2):
  cnt=0
  while M%j==0:
    cnt+= 1
    M = M//j
  if cnt!=0:
    e[j]=cnt
if M!=1:
  e[M]=1
for j in range(2,int(math.sqrt(N))+2):
  cnt=0
  while N%j==0:
    cnt+= 1
    N = N//j
  if cnt!=0:
    a[j]=cnt
if N!=1:
  a[N]=1
b = a.keys() & e.keys()
print(len(b)+1)

Submission status: Accepted

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

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

setA = set(factorize(A))
setB = set(factorize(B)) 
ans = len(setA & setB) + 1

print(ans)

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 = map(int, input().split())
maxDiv = gcd(a, b)

#print(maxDiv)

arr = prime_factorize(maxDiv)
sets = set()

for i in range(len(arr)):
    sets.add(arr[i])

#print(prime_factorize(maxDiv))
print(len(sets)+1)

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

ab=gcd(a,b)
li=make_divisors(ab)
li.sort()
n=len(li)//2+1
ans=0
for i in range(n):
    li2=make_divisors(li[i])
    if len(li2)<=2:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

a,b = na()

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
        
f = 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
    
d = factorization(f)
k = 1 if len(d) == 1 and d[0][0] == 1 else len(d)+1
print(k)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

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

def sol():
    A, B = map(int, input().split())

    primeA = primeCount(A)
    primeB = primeCount(B)

    ans = 1
    for a in primeA.keys():
        if a in primeB:
            ans += 1

    print(ans)

sol()

Submission status: Accepted

Solution code:
import sys
from _operator import itemgetter
from fractions import gcd

stdin = sys.stdin

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

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

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

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

    return divisors

a, b = na()
g = gcd(a, b)
li = make_divisors(g)
ct = 1
for num in li:
    if is_prime(num):
        ct += 1
print(ct)

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)+1)

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

a_pf = prime_factorize(a)
b_pf = prime_factorize(b)

pfs = set(a_pf)
pfs &= set(b_pf)
pfs.add(1)
print(len(pfs))

Submission status: Accepted

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

a, b = getList()

def koyak(a, b):
    koyak = []

    for i in range(1, int(math.sqrt(max(a, b))) + 1):
        if a % i == 0 and b % i == 0:
            koyak.append(i)

    return koyak

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

# ko = koyak(a, b)
ko = list((set(make_divisors(a)) & set(make_divisors(b))))
ko.sort()
ans = []
for k in ko:
    fl = True
    for an in ans:
        if k % an == 0 and an != 1:
            fl = False
            break
    if fl:
        ans.append(k)

# print(ko)
print(len(ans))

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
p = 2
def gcm(a,b):
    if a < b:
        return gcm(b,a)
    elif b == 0:
        return a
    else:
        return gcm(b,a%b)

g = gcm(a,b)

l = []
while p*p <= g:
    if g % p == 0:
        l.append(p)
        while g % p  == 0:
            g //= p
    p+=1

if g > 1:
    l.append(p)

print(len(l)+1)

Submission status: Accepted

Solution code:
import fractions
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 = fractions.gcd(A, B)
c = collections.Counter(prime_factorize(G)).keys()

print(len(list(c)) + 1)

Submission status: Accepted

Solution code:

A,B = map(int,input().split())
lis = []
lis2 = []
dic = {}

for i in range(10 ** 6):

    i += 1
    if A % i == 0:

        if B % i == 0 and i not in dic:

            dic[i] = 0
            lis.append(i)

        if B % (A // i) == 0 and A // i not in dic:
            lis.append(A // i)
            dic[A//i] = 0

lis.sort()

ans = []
#print (lis)

for i in lis:

    flag = True
    for j in ans:

        if i % j == 0 and j != 1:
            flag = False
            break

    if flag:
        ans.append(i)

#print (ans)
print (len(ans))

Submission status: Accepted

Solution code:
import fractions
import numpy as np

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(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= np.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

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

gcd = fractions.gcd(a, b)

yakusu = make_divisors(gcd)

num = 0
for i in yakusu:
    if i == 1:
        num += 1
    elif is_prime(i):
        num += 1

print(num)

Submission status: Accepted

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

A=[1]
B=[1]

for i in range(2,10**6+5):
    if a%i==0:
        A.append(i)
        while a%i==0:
            a//=i
if a!=1:
    A.append(a)
        
for i in range(2,10**6+5):
    if b%i==0:
        B.append(i)
        while b%i==0:
            b//=i
if b!=1:
    B.append(b)

ans=0
for i in range(len(A)):
    if A[i] in B:
        ans+=1
print(ans)

Submission status: Accepted

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

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

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

sy = sorted(list(yakusu(gcd(A, B))))
ans = []
for i in sy[1:]:
    flag = True
    for a in ans:
        if i % a == 0:
            flag = False
            break
    if flag:
        ans.append(i)
print(len(ans)+1)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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


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


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


div = get_div(gcd(a, b))
kouho = []
for i in range(len(div)):
    if div[i] == 1:
        continue
    if len(kouho) == 0:
        kouho.append(div[i])
        continue
    for x in range(len(kouho)):
        if div[i] % kouho[x] == 0:
            break
    else:
        kouho.append(div[i])
print(len(kouho)+1)