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 collections

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

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

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

gc = gcd(A, B)

c = collections.Counter(prime_factorize(gc))

print(len(c.keys()) + 1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  a,b=LI()

  if a==1 and b==1:
    return 1

  a=getPrimeList(a)
  b=getPrimeList(b)

  a=list(set(a))
  b=list(set(b))

  c=a+b
  c.sort()

  ans=1
  y=c[0]
  cnt=1
  for x in c[1:]:
    if x==y:
      cnt+=1
    else:
      y=x
      cnt=1

    if cnt==2:
      ans+=1

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
a,b=map(int,input().split())
tmp=gcd(a,b)
# print(tmp)
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=factorization(tmp)
# print(ans)
if tmp==1:
    print(1)
else:
    print(len(ans)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b=map(int,input().split())
m=gcd(a,b)
if m==1:print(1);exit()
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(len(pf.keys())+1)

Submission status: Accepted

Solution code:
import collections

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

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

AA=collections.Counter(prime_factorize(A))
BB=collections.Counter(prime_factorize(B))

AAA=list(AA)
BBB=list(BB)

CCC=set(AAA) & set(BBB)

print(len(CCC)+1)

Submission status: Accepted

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

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

import math

a, b = map(int, input().split())
c=gcd(a, b)
d=prime_factorize(c)
count=0
before=0
for i in range(len(d)):
    if d[i]!=before:
        count+=1
    before=d[i]

print(count+1)

Submission status: Accepted

Solution code:
a,b = (int(i) for i in input().split())
def gcd(a,b):
    if a%b: return gcd(b,a%b)
    else: return b
g = gcd(a,b)
num,ans = g,1
for i in range(2,int(g**0.5)+1):
    if num%i==0:
        ans+=1
        while num%i==0: num//=i
if num!=1: ans+=1
print(ans)

Submission status: Accepted

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

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

    # divisors.sort()
    return divisors

kou=make_divisors(sai)

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

ans=0
for i in kou:
    if is_prime(i):
        ans+=1
print(ans+1)

Submission status: Accepted

Solution code:
from fractions import gcd
A, B = map(int, input().split())
g = gcd(A, B)
def prime_factor(n):
    ass = set()
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ass.add(i)
        while n % i==0:
            n = n//i
    if n != 1:
        ass.add(n)
    return ass
ass = prime_factor(g)
print(len(ass)+1)

Submission status: Accepted

Solution code:
MAX_PRIME = 10**6
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor

a, b = map(int, input().split())
ans = 1
fa = factorization(a)
fb = factorization(b)
for p, _ in fa.items():
    if p in fb:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import*;g=gcd(*map(int,input().split()));d={};i=2
while i*i<=g:
    if g%i:i+=1
    else:g//=i;d[i]=d.get(i,0)+1
if g>1:d[g]=d.get(g,0)+1
print(len(d)+1)

Submission status: Accepted

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

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

print(len(pf)+1)

Submission status: Accepted

Solution code:

import  numpy as np
a,b = map(int,input().split())
def factorize(N):
    up = int(np.sqrt(N))+2
    out = {}

    for i in range(2,up):
        if N%i == 0:
            temp = N
            count = 0
            while(True):
                N = N//i
                count += 1
                if N%i != 0:
                    break
            out[i] = count
        else:
            continue
    if N != 1:
        out[N] = 1
    return out

a = factorize(a)
b = factorize(b)

sa = set()
sb = set()

for t in a:
    sa.add(t)
for t in b:
    sb.add(t)

t = sa&sb
print(len(t)+1)

Submission status: Accepted

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

import array
import collections
import fractions
import math


def sieve_of_eratosthenes(end, typecode="Q"):
    assert end > 1
    is_prime = array.array("B", (True for i in range(end)))
    is_prime[0] = False
    is_prime[1] = False
    primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def factorize_trial_division(n, typecode="Q"):
    factors = array.array(typecode)
    if n < 2:
        return factors
    for p in sieve_of_eratosthenes(math.ceil(math.sqrt(n)) + 1):
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def compute_max_size(a, b):
    g = fractions.gcd(a, b)
    fs = factorize_trial_division(g)
    ctr = collections.Counter(fs)
    res = len(ctr) + 1
    return res


def main():
    a, b = (int(c) for c in input().split())
    res = compute_max_size(a, b)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    return arr
arr=factorization(gcd(a,b))
print(1+len(arr))

Submission status: Accepted

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


primes = [1] * (10 ** 6 + 1)
primes[0] = 0
primes[1] = 0
for p in range(10 ** 3 + 1):
    if primes[p]:
        for n in range(p * p, 10 ** 6 + 1, p):
            primes[n] = 0
prime_list = [p for p in range(10 ** 6 + 1) if primes[p] == 1]


def solve_d(a, b):
    d = gcd(a, b)
    res = 1
    for p in prime_list:
        if d % p == 0:
            res += 1
        while d % p == 0:
            d = d // p
    if d > 1:
        res += 1

    return res


def main():
    a, b = map(int, input().split())
    res = solve_d(a, b)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  L = []
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        L.append(i)
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
    L.append(x)
  return L


a = prime(A)
b = prime(B)

ans = 1

for i in a:
  if i in b:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

from math import floor
# 約数全列挙(ソート済み)
# n = 24 -> [1,2,3,4,6,8,12,24]
def divisor(n):
    left = [1]
    right = [n]
    sup = floor(pow(n,1/2))
    for p in range(2,sup+1):
        if n % p == 0:
            if p == n//p:
                left.append(p)
                continue
            left.append(p)
            right.append(n//p)
    res = left + right[::-1]
    return res

def is_prime(n):
    if n <= 0: return None
    if n == 1: return False
    sup = floor(pow(n,1/2))
    for i in range(2,sup+1):
        if n % i == 0:
            return False
    return True

A, B = map(int,input().split())
G = gcd(A, B)
if G == 1:
    print(1)
    exit()
res = divisor(G)
ans = 0
for d in res:
    if d == 1 or is_prime(d):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



def prime_decomposition(n):
    table =[]
    i = 2
    while n >= i**2:
    # nのその数自身を除いた素因数は√n以下であることから。
        while n % i == 0:
            table.append(i)
            n /= i
        i += 1
    if n > 1:
        table.append(int(n))
# 最後に残った、最大の素因数をリストに入れる。
    return table


a, b = LI()
print(len(set(prime_decomposition(gcd(a, b)))) + 1)

Submission status: Accepted

Solution code:
#D問題
#gcd(二つの数)
def gcd(GCD1,GCD2):
    x = min(GCD1,GCD2)
    y = max(GCD1,GCD2)
    if y%x == 0:
        return x
    else:
        return gcd(x,y%x)

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

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

li = prime_factorize(G)
#print(li)
print(len(li)+1)

Submission status: Accepted

Solution code:
from fractions import gcd

def factorize2(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    >>> factorize(20)
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b * b <= n:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


A, B = map(int, input().split())
cnt = 1
for num, pow in factorize2(gcd(A, B)):
    cnt += 1
print(cnt)

Submission status: Accepted

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

from fractions import gcd

def divisors(num):
    """
    約数全列挙
    """
    divisors = []
    for i in range(1, int(num ** 0.5) + 1):
        if num % i == 0:
            divisors.append(i)
            if i != num // i:
                divisors.append(num // i)

    return divisors

a_d = set(divisors(A))
b_d = set(divisors(B))

c_set = a_d & b_d
c_list = sorted(list(c_set))
used = []
for k in c_list:
    if len(used) != 0:
        f = False
        for u in used:
            if gcd(u, k) != 1:
                f = True
                break
        if not f:
            used.append(k)
    else:
        used.append(k)
print(len(used))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def trial_division(n):
    factor=[]
    sqrt=int(n**.5)+1 # sqrt=ceil(sqrt(n))
    for d in range(2,sqrt):
        while(n%d==0):
            n//=d
            factor.append(d)
    if n==1: return factor
    else: return factor+[n]
def resolve():
    from fractions import gcd
    a,b=map(int,input().split())
    g=gcd(a,b)
    print(len(set(trial_division(g)))+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

A, B = map(int, input().split())
s1 = set()
for i in range(2, int(math.sqrt(A))+1):
    if A % i == 0:
        s1.add(i)
        while A % i == 0:
            A //= i
if A > 1:
    s1.add(A)
s2 = set()
for i in range(2, int(math.sqrt(B))+1):
    if B % i == 0:
        s2.add(i)
        while B % i == 0:
            B //= i
if B > 1:
    s2.add(B)
print(len(s1&s2)+1)

Submission status: Accepted

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

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

gcd = fractions.gcd(A, B)
c = collections.Counter(prime_factorize(gcd))

print(len(c.keys()) + 1)

Submission status: Accepted

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

def fact(n):
  l=primes(int(n**0.5)+1)
  L=[]
  for i in range(len(l)):
    while n%l[i]==0:
      n=n//l[i]
      L.append(l[i])
    if n==1:
      break
  if n!=1:
    L.append(n)
  return L

import sys
a,b=map(int,input().split())
if a==1 or b==1:
  print(1)
  sys.exit()
a2=list(set(fact(a)))
b2=list(set(fact(b)))
ct=1
for i in range(len(a2)):
  if a2[i] in b2:
    ct+=1
print(ct)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
while b != 0:
  a,b = b,a%b
pr = set()
i = 2
while i ** 2 <= a:
  while a % i == 0:
    a //= i
    pr.add(i)
  i += 1
pr.add(a)
pr.add(1)
print(len(pr))

Submission status: Accepted

Solution code:
import fractions
import math

[a,b] = [int(i) for i 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

c = fractions.gcd(a,b)
ls = make_divisors(c)

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

cnt = 1

for i in range(len(ls)):
    if is_prime(ls[i]):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

from collections import Counter

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 main():
    a, b = LI()
    a_s = prime_factorize(a)
    b_s = prime_factorize(b)
    a_keys = set(Counter(a_s).keys())
    b_keys = set(Counter(b_s).keys())
    print(str(1 + len(a_keys & b_keys)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

gc = gcd(a,b)
#print(gc)

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

ko = factorization(gc)
if gc == 1:
    print(len(ko))
else:
    print(len(ko)+1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
def factorize2(n): # 素因数分解　2次元素数リスト([素数,指数])
    i = 2
    m = 1
    table = []
    sign = -1
    while i * i <= n:
        j = 0
        while n % i == 0:
            n //= i
            j += 1
        if j != 0:
            table.append([i,j])
        if i >= 5:
            if sign < 0:
                sign = 1
                i = 6*m + sign
            else:
                m += 1
                sign = -1
                i = 6*m + sign
        elif i == 2:
            i += 1
        elif i == 3:
            i = 5
    if n > 1:
        table.append([n,1])
    return table # list
AL = [i[0] for i in factorize2(A)]
BL = [i[0] for i in factorize2(B)]
ans = len(set(AL)&set(BL))+1
print(ans)

Submission status: Accepted

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

from fractions import gcd
g = 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

gg = prime_factorize(g)
print(len(list(set(gg))) + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(A: int, B: int):
    def count(n):
        ret = 1
        i = 2
        while i * i <= n:
            if n % i == 0:
                ret += 1
                while n % i == 0:
                    n //= i
            i += 1
        if n > 1:
            ret += 1
        return ret
    def gcd(a, b):
        if b == 0:
            return a
        return gcd(b, a % b)
    g = gcd(A, B)
    #print(g)
    ret = count(g)
    print(ret)
    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:
A,B = map(int,input().split())
def factoring(M,n=2):
    for i in range(n,int(M**0.5)+1):
        if M%i==0:
            ret = factoring(M//i,i)
            ret[i] = ret.get(i,0)+1
            return ret
    return {M:1}
print(len(set(factoring(A).keys()) & set(factoring(B).keys())) + (1-(A==B==1)))

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
def calcgcd(a, b):
  if a > b:
    a, b = b, a
  while a > 0:
    a, b = b%a, a
  return b
N = calcgcd(A, B)
n = N
fs = []
f = 2
while n > 1:
  if f*f > n:
    fs.append(n)
    n = 1
  elif n%f == 0:
    fs.append(f)
    n = n//f
  else:
    f += 1
#print(N, fs)
r = len(set(fs))+1
print(r)

Submission status: Accepted

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

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

#la = prime_factorize(a)
#lb = prime_factorize(b)
#print(la, lb)

c = fractions.gcd(a, b)
lc = prime_factorize(c)
#print(c, lc)

ans = list(set(lc))
ans = len(ans) + 1
print(ans)

Submission status: Accepted

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

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

def factorization(num):
    import math
    # 因数分解した結果をタプルのリストで返す
    # [(prime, count), ...]
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu

def main():
    A, B = map(int, input().split())
    gcd_ = gcd(A, B)

    insu = factorization(gcd_)
    print(len(insu) + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

# 素因数分解
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n

A,B = map(int,input().split())
g = gcd(A,B)
print(1+len(set(prime_factors(g))))

Submission status: Accepted

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


a, b = [int(i) for i in input().split()]
c = gcd(a, b)

def d(x):
    i = 2
    e=[]
    while True:
        if x % i == 0:
            e.append(i)
            while x % i == 0:
                x //= i
        if i * i > x:
            break
        i+=1
    if x != 1:
        e.append(x)
    return e
print(len(d(c))+1)

Submission status: Accepted

Solution code:
from subprocess import*
a,b=map(int,input().split())
x=set(map(int,Popen(['factor',str(a)],stdout=PIPE).communicate()[0].decode().split()[1:]))
y=set(map(int,Popen(['factor',str(b)],stdout=PIPE).communicate()[0].decode().split()[1:]))
print(len(x&y)+1)

Submission status: Accepted

Solution code:
from fractions import gcd


def prime_factorize(num): # 整数に対し素因数分解
    prime_factor = {}
    i = 2
    while i ** 2 <= num:
        while num % i == 0:
            num //= i
            if i in prime_factor.keys():
                prime_factor[i] += 1
            else:
                prime_factor[i] = 1
        i += 1
    if num > 1:
        prime_factor[num] = 1
    return prime_factor
a,b = map(int,input().split())
x = gcd(a,b)

data = prime_factorize(x)
print(len(data)+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 primeFactorization(n):
	res = {}
	m = int(n**0.5)
	for i in range(2,m+1):
		cnt = 0
		while n % i == 0:
			n = n//i
			cnt+=1
		if cnt > 0:
			res[i] = cnt
	if n > 1:
		res[n] = 1
	return res

N = gcd(A,B)
f = primeFactorization(N)

print(len(f)+1)

Submission status: Accepted

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

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

g = gcd(A,B)

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

fct = factorize(g)

print(len(fct)+1)

Submission status: Accepted

Solution code:
import collections
import math


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


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


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

sieve = eratosthenes(math.ceil(math.sqrt(c)))
counter = collections.Counter()
for i in range(1, c):
    if i**2 > c:
        break
    if sieve[i]:
        while c % i == 0:
            counter[i] += 1
            c //= i
if c > 1:
    counter[c] += 1
print(len(counter) + 1)

Submission status: Accepted

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

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

ans = 1 + len(fctr1(m))
print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def primeFact(n):
    factors = set()
    factors.add(1)
    i = 2
    while i*i <= n:
        if n % i == 0:
            n //= i
            factors.add(i)
        else:
            i += 1
    if n > 1:
        factors.add(n)
    return factors


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

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
d=gcd(a,b)
pf={}
for i in range(2,int(d**0.5)+1):
  while d%i==0:
    pf[i]=pf.get(i,0)+1
    d//=i
if d>1:
  pf[d]=1
P=list(pf.keys())
print(len(P)+1)

Submission status: Accepted

Solution code:
def factorize(n):
    a = 2
    fct = []
    while a * a <= n:
        while n % a == 0:
            n //= a
            fct.append(a)
        a += 1
    if n > 1:
        fct.append(n)
    return fct


a, b = map(int, input().split())
print(len(set(factorize(a)) & set(factorize(b))) + 1)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



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

def main():
    num_a, num_b = map(int, input().split())
    yakusuu_a = divisor(num_a)
    yakusuu_b = divisor(num_b)

    yakusuu = yakusuu_a & yakusuu_b
    yakusuu = list(yakusuu)
    yakusuu.sort()
    ans = set()
    for ele in yakusuu:
        for ele2 in ans:
            if ele2 == 1:
                continue
            if ele % ele2 == 0:
                break
        else:
            ans.add(ele)

    print(len(ans))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
import math
import collections


def factorial(n):
    # 試し割りによる素因数分解
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def solve(A: int, B: int):
    As = factorial(A)
    Bs = factorial(B)
    counter = 1
    for key in As:
        if key in Bs:
            counter += 1
    print(counter)
    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()