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

a,b = map(int,input().split())
x = math.gcd(a,b)
s = [1]
for i in range(2,int(math.sqrt(x)+1)):
    if x%i == 0:
        while x%i == 0:
            x //= i
        s.append(i)
if x != 1:
    s.append(x)
l = len(s)
print(l)

Submission status: Accepted

Solution code:
from functools import lru_cache

def main():
    a,b=map(lambda x: set(prime_factorize(int(x))),input().split())
    print(len(a&b)+1)

@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

# 素数判定（単純な素数判定なら十分早い。大量にやる場合はX in primesがよさそう）
@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

# 素因数分解
@lru_cache(maxsize=None)
def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    # 2で割り続け奇数まで還元する
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    # sqrt(n)までの素数で試し割
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

#約数リスト
def make_divisors(n: int) -> list:
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
        
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

from math import gcd

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    def factorization(n):
        if n==1:
            return []
        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
    
    mod=10**9+7
    a,b=MI()
    from math import gcd
    g=gcd(a,b)
    arr=factorization(g)
    
    ans=len(arr)+1
    
    print(ans)
    
    
    

main()

Submission status: Accepted

Solution code:
import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

# 素因数,個数 の組リストを出力
def fctr1(n): 
    f = []
    c = 0
    r = int(n**0.5)
    for i in range(2,r+2):
        while n%i == 0:
            c += 1 
            n = n//i
        if c != 0:
            f.append([i,c])
            c = 0
    if n != 1:
        f.append([n,1])
    return f

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

print(len(fctr1(math.gcd(a,b)))+1)

Submission status: Accepted

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

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#nを素因数分解したリストを返す
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

print(len(factorization(gcd(a,b)))+1 if gcd(a,b)!=1 else 1)

Submission status: Accepted

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

n = gcd(A, B)
ans = factorize(n)
if ans[0][0] == 1:
    print(1)
    exit()
print(len(ans)+1)

Submission status: Accepted

Solution code:
import math
def gcd(a,b):
    if a==0: return b
    return gcd(b%a,a)
def div(n):
    cnt = 0
    temp = n
    for i in range(2,int(math.sqrt(n))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            cnt += 1
    if temp!=1:
        cnt+=1
    return cnt+1

a,b = map(int,input().split())
print(div(gcd(a,b)))

Submission status: Accepted

Solution code:
import math
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())
Af = factorization(A)
Bf = factorization(B)
As = set()
Bs = set()
for i in range(len(Af)):
    As.add(Af[i][0])
for j in range(len(Bf)):
    Bs.add(Bf[j][0])
if A == 1 and B ==1:
    print(1)
else:
    print(len(As & Bs)+1)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
def factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return set(a)
print(len(factorize(a)&factorize(b))+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

A = set(prime_factorize(a))
B = set(prime_factorize(b))

cnt = 0
for i in A:
    if i in B:
        cnt += 1
print(cnt+1)

Submission status: Accepted

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

plist = []

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

print(len(plist) + 1)

Submission status: Accepted

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

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

a = fact(A)
b = fact(B)
ans = 0
for i in a:
	if i in b:
		ans += 1


print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def gcd(a, b):
    """最大公約数"""
    a, b = (a, b) if a >= b else (b, a)
    if b == 0:
        return a
    return gcd(b, a % b)


def prime_factorization(x):
    """素因数分解"""
    import math
    re = []
    i = 2
    while x != 1:
        if x % i == 0:
            re.append(i)
            x //= i
        else:
            i += 1
            if i > math.sqrt(x):
                re.append(x)
                break
    return re


# from decorator import stop_watch
#
#
# @stop_watch
def solve(A, B):
    div = gcd(A, B)
    print(len(set(prime_factorization(div))) + 1)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    A, B = map(int, input().split())
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    # print(prime_factorization(A))
    # print(prime_factorization(B))
    solve(A, B)

Submission status: Accepted

Solution code:
# 問題：https://atcoder.jp/contests/abc142/tasks/abc142_d

import math

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


def count_prime_factorize(n):
    res = 1
    i = 2
    while i ** 2 <= n:
        if n % i == 0:
            res += 1
            while n % i == 0:
                n //= i
        i += 1
    if n != 1:
        res += 1
    return res


a, b = map(int, input().strip().split())
x = gcd(a, b)
res = count_prime_factorize(x)
print(res)

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

from math import sqrt
from math import gcd
a, b = map(int, input().split())
x = gcd(a, b)
print(len(set(prime_factorize(x)))+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


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

lst=make_divisors(a)
sin_lst=[]

for i in lst:
  if b%i==0:
    sin_lst.append(i)

if len(sin_lst)==1:
  print(1)
  exit()

lst=[]
lst.append(sin_lst[1])

for i in sin_lst[2:]:
  flag=True
  for j in lst:
    if i%j==0:
      flag=False
      break
  
  if  flag:
    lst.append(i)


print(len(lst)+1)

Submission status: Accepted

Solution code:
import fractions
import sys
sys.setrecursionlimit(10**9)


INF=10**20
def prime_factorize(n):
    P = []
    P_set = set()
    while n % 2 == 0:
        P.append(2)
        P_set.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            P.append(f)
            P_set.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        P.append(n)
        P_set.add(n)

    P_count = {p:0 for p in P_set}
    for p in P: P_count[p] += 1

    return P_count


def solve(A: int, B: int):
    gcd = fractions.gcd(A,B)
    P = prime_factorize(gcd).keys()
    print(len(list(P))+1)
    return

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 gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
a, b = map(int, input().split())
n = gcd(a, b)
primes = []
MAX = 10 ** 6 + 10
is_prime = [False] * 2 + [True] * (MAX - 2)
for i in range(2, MAX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MAX, i):
            is_prime[j] = False
cnt = 1
for p in primes:
    if n % p == 0:
        cnt += 1
        while n % p == 0:
            n /= p
if n != 1:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import math

A, B = [int(_) for _ in input().split()]
N = math.gcd(A, B)

ans = 1
for i in range(2, int(math.sqrt(N)+1) + 1):
    if N % i == 0:
        ans += 1
        while N % i == 0:
            N //= i
if N > 1:
    ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
A, B = map(int, input().split())
g = gcd(A, B)
ans = 1
n = 2
while g > 1:
  if n * n > g:
    ans += 1
    break
  if g % n == 0:
    ans += 1
  while g % n == 0:
    g //= n
  n += 1
print(ans)

Submission status: Accepted

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

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

p = gcd(a, b)
factors = {}

while p > 1:
    f = False
    for i in range(2, int(p**0.5)+1):
        if p % i == 0:
            if i in factors:
                factors[i] += 1
            else:
                factors[i] = 1

            p //= i
            f = True
            break

    if not f:
        if p in factors:
            factors[p] += 1
        else:
            factors[p] = 1
        break

print(len(factors)+1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    N=GCD
    
    cnt = 0
    
    ls=[]
    
    for n in range(2,int(N**0.5)+2):
 
        if GCD % n == 0:
            cnt += 1
 
            while GCD % n == 0:
                GCD = GCD//n
                ls.append(n)
        
    if GCD == 1:
        print(cnt+1)
    else:
        print(cnt+2) 

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def divisors(x):
    l = [[], []]
    for i in range(1, int(math.sqrt(x))+1):
        if x % i == 0:
            if i**2 != x:
                l[0].append(i)
                l[1].append(x//i)
            else:
                l[0].append(i)
    return l[0]+l[1][::-1]

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

a, b = map(int, input().split())
cnt = 0
for i in divisors(math.gcd(a, b)):
    if i == 1:
        cnt += 1
    elif primenumber(i):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from math import gcd
import random
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


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

    # n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    # 判定をk回繰り返す
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        # [0,s-1]の範囲すべてをチェック
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

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())
l = make_divisors(gcd(A, B))
_l = factorization(gcd(A, B))
ans = 0
#print(gcd(A, B))
#print(l)
#print(_l)
for num in l:
    if is_prime3(num):
        #print(num)
        ans += 1
print(ans + 1)

Submission status: Accepted

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

# 最大公約数（ユークリッドの互除法）
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):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

print(len(factorization(gcd(a,b)))+1 if a!=1 and b!=1 else 1)
# print(gcd(a,b))
# print(factorization(gcd(a,b)))

Submission status: Accepted

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

# 最大公約数（ユークリッドの互除法）
def gcd(A,B):
    while B!=0:
        A,B=B,A%B
    return A

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

print(len(factorization(gcd(a,b)))+1 if a!=1 and b!=1 else 1)
# print(gcd(a,b))
# print(factorization(gcd(a,b)))

Submission status: Accepted

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

# input = stdin.readline


def main():
  A,B = map(int,input().split())
  def primeLst(x):
    acc = []
    f = 2
    while f * f <= x:
      if x % f == 0:
        acc.append(f)
        x //= f
      else:
        f += 1
    if x != 1:
      acc.append(x)
    return acc
  a = set(primeLst(A))
  b = set(primeLst(B))
  if len(a) * len(b) == 0:
    ans = 1
  else:
    ans = len(a&b) + 1
  print(ans)
  return

if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

cnt = len(set(prime_decomposition(x)))

print(cnt+1)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
import math
c=math.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
print(len(set(prime_factorize(c)))+1)

Submission status: Accepted

Solution code:
def factrization(n):
    arr = []
    temp = n
    
    for i in range(2, int(n**0.5//1) + 2):
        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 = map(int, input().split())
ans = 0

la = factrization(a)
lb = factrization(b)

if 1 not in la:
    la.append(1)
if 1 not in lb:
    lb.append(1)

for i in la:
    if i in lb:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

n=math.gcd(a,b)

cnt=1

f=2
d=n
while f*f<=n:
    if d%f==0:
        cnt+=1
        while d%f==0:
            d=d//f
    f+=1
if d!=1:
    cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353
import numpy

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

c = math.gcd(A, B)
d = factorization(c)

if c > 1:
    print(len(d)+1)
else:
    print(1)

Submission status: Accepted

Solution code:
import math

a,b = map(int, input().split())
t = math.gcd(a,b)

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

cnt = len(set(prime_decomposition(t)))

print(cnt+1)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
A=[1]
for i in range(2,int(a**0.5)+1):
    if a%i==0:
        while a%i==0:
            a//=i
        A.append(i)
if a>1:
    A.append(a)
B=[1]
for i in range(2,int(b**0.5)+1):
    if b%i==0:
        while b%i==0:
            b//=i
        B.append(i)
if b>1:
    B.append(b)
can=0
for i in A:
    if i in B:
        can+=1
print(can)

Submission status: Accepted

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

def fact(n):
    k = 2
    l = [] 
    temp=n
    while pow(k, 2)<=n:
        if temp%k==0:
            l.append(k)
            while temp%k==0:
                temp//=k
        k+=1
    if temp!=1:
        l.append(temp)
    return l

if A==1 and B==1:
    print(1)
elif A==B:
    print(len(set(fact(A)))+1)
else:
    print(len(set(fact(A))&set(fact(B)))+1)

Submission status: Accepted

Solution code:
import math

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

def isPrime(x):
    if x < 2:
        return 0
    elif x == 2:
        return 1
    if x%2 == 0:
        return 0
    ir=int(x**(0.5))+1
    for i  in range(3,ir,2) :
        if x%i == 0:
            return 0
    return 1

a,b=map(int,input().split())
c=math.gcd(a,b)

if isPrime(c)==1:
    print(2)
else:
    icnt=0
    for i in enum_div(c):
        if isPrime(i)==1:
            icnt+=1
    print(icnt+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 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

t = factorization(gcd(a,b))
if t[0][0]==1:
    print(1)
    exit()
print(len(t)+1)

Submission status: Accepted

Solution code:
import math


def main():
    a, b = map(int, input().split())
    gcd = math.gcd(a, b)
    ans = [1]
    while gcd % 2 == 0:
        ans.append(2)
        gcd = gcd // 2
    f = 3
    while f * f <= gcd:
        if gcd % f == 0:
            ans.append(f)
            gcd = gcd // f
        else:
            f += 2
    if gcd != 1:
        ans.append(gcd)
    print(len(set(ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math 
def using_sqrt(k):  
    factor = 0
        
    # 2以外の偶数は素数ではないので無視する
    if k % 2 == 0 and k != 2:
        return False
        
    # 繰り返しの上限を対象の平方根にする
    for divisor in range(2, math.floor(math.sqrt(k))+1):
        if k % divisor == 0:
            factor += 1
                
    if factor == 0:
        return True
    else:
        return False
            
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_codivisors(n):
    divisors = []
    n0divisors = make_divisors(n[0])
    n0len = len(n0divisors)
    for i in n0divisors:
        for j in range(1, len(n)):
            if n[j] % i != 0:
                break
            if j == len(n)-1:
                divisors.append(i)
            
    # divisors.sort()
    return divisors

a, b =map(int, input().split())
div = make_codivisors([a, b])
ans = 0
for i in div:
  if i==1:
    ans+=1
  else:
    if using_sqrt(i):
      ans+=1
print(ans)

Submission status: Accepted

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

A , B = ( int(x) for x in input().split() )

Gcd = gcd( A , B )
lo_cds = []
up_cds = []
i = 1
while i * i <= Gcd:
    if Gcd % i == 0:
        lo_cds.append(i)
        if Gcd // i != i:
            up_cds.append( Gcd // i )
    i += 1
Cds = lo_cds + up_cds[::-1]
# 1は必ず含まれるし素数判定の邪魔なので事前に省く。
Cds.pop(0)
i = 0


while i < len(Cds):
    j = i + 1
    while j < len(Cds):
        if Cds[j] % Cds[i] == 0:
            Cds.pop(j)
        else:    
            j += 1
    i += 1

print( len(Cds) + 1 )

Submission status: Accepted

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

Submission status: Accepted

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

gcd = math.gcd(A,B)
d = []
if A == 1 or B == 1 :
    print(1)
    exit()
ans = [1]
while gcd %2 == 0 :
    gcd //= 2
    ans.append(2)
i = 3
while i * i <= gcd :
    if gcd %i == 0 :
        ans.append(i)
        gcd //= i
    else :
        i += 2
if gcd != 1 :
    ans.append(gcd)
print(len(set(ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


a,b = list(map(int, input().split()))
def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr
fa = factor(a)
fb = factor(b)
if 1 in fa:
    del fa[1]
if 1 in fb:
    del fb[1]
d = set(list(fa.keys())) & set(list(fb.keys()))
ans = len(d) + 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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

"""
gを素因数分解したときの素因数のリストの要素数 + 「1」を含める

g == 1のとき
1
g != 1のとき
素因数リストの要素数 +1
"""



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


gdlist = prime_factorize(g)
if gdlist ==[]:
    print(1)
else:
    print(len(set(gdlist))+1)

Submission status: Accepted

Solution code:
n, m = 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 = sorted(list(set(table)))
    return table


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


s = set(divisor(n)).intersection(set(divisor(m)))

ans = 1
for ss in s:
    if len(prime_factorize(ss)) == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
x=math.gcd(a,b)
bun=[0]*(int(math.sqrt(x)+1))
bun[1]=1
for i in range(2,len(bun)):
  while x%i==0:
    if bun[i]==0:
      bun[i]+=1
    x=x//i
ans=sum(bun)
if x>1:
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import math
    a,b = map(int,input().split())
    g = math.gcd(a,b)
    ans = [1]
    for m in range(2,int(g**0.5)+1):
        if g%m==0:
            ans.append(m)
            while g%m==0:
                g = g//m
        if g==1:
            break
    if g!=1:
        ans.append(g)
    print(len(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
sa = set()
sb = set()
i = 1
while i * i <= max(a,b):
    if a % i == 0:
        sa.add(i)
        sa.add(a//i)
    if b % i == 0:
        sb.add(i)
        sb.add(b//i)
    i += 1
s = sa & sb
s.remove(1)
for x in list(s):
    for y in list(s):
        if x == y:
            continue
        if y % x == 0:
            s.remove(y)
print(len(s) + 1)

Submission status: Accepted

Solution code:
import math
#https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
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())
g = math.gcd(a,b)
if g==1:
    print(1)
else:
    yakusu = factorization(g)
    print(len(yakusu)+1)