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 fractions
import itertools
import math

# nの約数をすべて求める
def make_divisors(n):
    divisors = set()
    #for i in range(1, int(n**0.5)+1):
    for i in itertools.takewhile(lambda i: i**2<=n, itertools.count(1)):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    
    return divisors

# 素因数分解
# 素因数とその指数をペアにして配列で返す
def factorize(n):
    # 素因数の候補
    # i=2,...,floor(sqrt(n)) つまりi**2<=nになるまで
    remainder = n
    ret = set()
    for i in itertools.takewhile(lambda i: i**2<=n, itertools.count(2)):
        # 現在の余りをiで割れるだけ割る
        if remainder % i:
            continue
        else:
            # 割れるなら，割れる回数と余りを求める
            p = 0
            while remainder % i == 0:
                remainder //= i
                p += 1

            ret.add((i,p))

    # 2以上の余りが残っていれば，追加
    if remainder > 1: ret.add((remainder,1))

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

# 答えの集合は1or素数で構成されるとして良い (a*b,a>1,b>1となる要素があれば，aも公約数だから，a*bをaに置き換えても最適解になるから)
# つまり，A,Bをそれぞれ素因数分解し，共通の素因数の数を数えればよい
# これは，gcd(A,B)の素因数の数と同じ
gcd = fractions.gcd(A,B)
divs = factorize(gcd)
print(len(divs) + 1) # + 1は"1"の数

Submission status: Accepted

Solution code:
import fractions
import itertools
import math

# nの約数をすべて求める
def make_divisors(n):
    divisors = []
    #for i in range(1, int(n**0.5)+1):
    for i in itertools.takewhile(lambda i: i**2<=n, itertools.count(1)):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors

# 素因数分解
# 素因数とその指数をペアにして配列で返す
def factorize(n):
    # 素因数の候補
    # i=2,...,floor(sqrt(n)) つまりi**2<=nになるまで
    remainder = n
    ret = []
    for i in itertools.takewhile(lambda i: i**2<=n, itertools.count(2)):
        # 現在の余りをiで割れるだけ割る
        if remainder % i:
            continue
        else:
            # 割れるなら，割れる回数と余りを求める
            p = 0
            while remainder % i == 0:
                remainder //= i
                p += 1

            ret.append((i,p))

    # 2以上の余りが残っていれば，追加
    if remainder > 1: ret.append((remainder,1))

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

# 答えの集合は1or素数で構成されるとして良い (a*b,a>1,b>1となる要素があれば，aも公約数だから，a*bをaに置き換えても最適解になるから)
# つまり，A,Bをそれぞれ素因数分解し，共通の素因数の数を数えればよい
# これは，gcd(A,B)の素因数の数と同じ
gcd = fractions.gcd(A,B)
divs = factorize(gcd)
print(len(divs) + 1) # + 1は"1"の数

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

def factorize(n: int) -> int:
    b = 2
    ret = []
    while b*b <= n:
        while n%b == 0:
            n //= b
            ret.append(b)
        b = b + 1

    if n > 1:
        ret.append(n)

    return list(set(ret))

g = fractions.gcd(a, b)
print(len(factorize(g))+1)

Submission status: Accepted

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

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

C = list(set(make_divisors(A)) & set(make_divisors(B)))
C.sort()

for i in range(1, len(C) - 1):
  a = C[i]
  for j in range(len(C) - 1, i, -1):
    if C[j] % a == 0:
      del C[j]
  if i + 1 >= len(C):
    break
    
print(len(C))

Submission status: Accepted

Solution code:
import fractions
import itertools

# nの約数をすべて求める
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

# 最大公約数gcd
gcd = fractions.gcd(A,B)
# 公約数=最大公倍数gcdの約数
cd = make_divisors(gcd)
cd = sorted(cd)

# 小さいものから1つずつ
ans = set()
for x in cd:    
    if len(ans) == 0:
        # 集合が空なら
        ans.add(x)
    else:
        # 集合のどの要素ともxが互いに素なら，追加
        if all([fractions.gcd(x,y)==1 for y in ans]):
            ans.add(x)

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

Submission status: Accepted

Solution code:
from fractions import gcd

def prime_factorize(n):
  factor = []
  for i in range(2, int(n**0.5)+1):
    while n % i == 0:
      n //= i
      factor.append(i)
  if n != 1:
    factor.append(n)
  return factor

A, B = map(int, input().split())
N = gcd(A, B)
l = set(prime_factorize(N))
print(len(l)+1)

Submission status: Accepted

Solution code:
def makeDivisors(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 isPrime(n):
    for i in range(2, n+1):
        if i**2 > n:
            break
        if n % i == 0:
            return False
    return True

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

div_A = makeDivisors(A)
div_B = makeDivisors(B)

common_divisors = list(set(div_A) & set(div_B))

count = 0
for i in common_divisors:
    if isPrime(i):
        count += 1

print(count)

Submission status: Accepted

Solution code:
def primes(n):
    i = 2
    prime = []
    while i**2<= n:
        if n % i:
            i += 1
        else:
            n =n//i
            prime.append(i)
    if n > 1:
        prime.append(n)
    return prime
a,b=map(int,input().split())
pa=set(primes(a))
pb=set(primes(b))
inte=pa.intersection(pb)
print(len(inte)+1)

Submission status: Accepted

Solution code:
import math
def primes(n):
    l= []
    for i in range(2,math.floor(math.sqrt(n))):
        while n % i == 0:
            n = n//i
            l.append(i)
        if n == 1: 
            break
    
    if n > 1:
        l.append(n)
    return l

a,b=map(int,input().split())
sa=set(primes(a))
sb=set(primes(b))
sans=sa.intersection(sb)
print(len(sans)+1)

Submission status: Accepted

Solution code:
def primes(n):
    i = 2
    factors = []
    while i**2<= n:
        if n % i:
            i += 1
        else:
            n =n//i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
a,b=map(int,input().split())
sa=set(primes(a))
sb=set(primes(b))
sans=sa.intersection(sb)
print(len(sans)+1)

Submission status: Accepted

Solution code:
import math
import collections

def LI():
  return [int(s) for s in input().split()]

A,B = LI()

prime_factor = []

for i in range(2,int(math.sqrt(A))+1):
  while A%i == 0:
    prime_factor.append(i)
    A/=i

if A > 1:
  prime_factor.append(A)

prime_factor.append(1)
c1 = set(prime_factor)

prime_factor = []

for i in range(2,int(math.sqrt(B))+1):
  while B%i == 0:
    prime_factor.append(i)
    B/=i
    
if B > 1:
  prime_factor.append(B)

prime_factor.append(1)
c2 = set(prime_factor)

N = len(c1 & c2)

print(N)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
while a%b != 0:
  a, b = b, a%b
ans = 1
if b%2==0:
  ans += 1
  while b%2==0:
    b = b//2
for i in range(3, int(b**0.5)+1, 2):
  if b%i==0:
    ans += 1
    while b%i==0:
      b = b//i
if b != 1:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
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
x=gcd(a,b)
l=prime_factorize(x)
l=set(l)
print(len(l)+1)

Submission status: Accepted

Solution code:

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

from fractions import gcd
import math
from collections import Counter
from itertools import combinations

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

G = gcd(A, B)
if G == 1:
  print(1)
  exit()

D = [1] + list(Counter(prime_factorize(G)).keys())
print(len(D))

Submission status: Accepted

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

def prime_factors(N): #素因数#エラーある
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            while tmp%i == 0:
                tmp //= i
            ret.append(i)
    if tmp != 1:
        ret.append(tmp)
    return ret


    
def main():
    a, b = map( int, input().split())
    d = gcd(a,b)
#    print(2, is_prime(2))
    if d == 1:
        print(1)
        return

    print(len(prime_factors(d))+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def factors(N): #約数を全て求める。ただし、順不同
    ret = 1
    middle = int( N**(1/2))
    tmp = N
    # if tmp%2 == 0:
    #     while tmp%2 == 0:
    #         tmp //= 2
    for i in range(2, middle+1):
        if tmp%i == 0:
            ret += 1
            while tmp%i == 0:
                tmp //= i
    if tmp != 1:
        ret += 1
    return ret

    
def main():
    a, b = map( int, input().split())
    d = gcd(a,b)
#    print(2, is_prime(2))
    if d == 1:
        print(1)
        return

    print(factors(d))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def factors(N): #約数を全て求める。ただし、順不同
    from collections import deque
    ret = 0
    middle = int( N**(1/2))
    for i in range(1, middle):
        if N%i == 0:
            if is_prime(i):
                ret += 1
            if is_prime(N//i):
                ret += 1
            
    if N%middle == 0:
        if is_prime(middle):
            ret += 1
        if middle != N//middle:
            if is_prime(N//middle):
                ret += 1
    return ret

    
def main():
    a, b = map( int, input().split())
    d = gcd(a,b)
#    print(2, is_prime(2))
    if d == 1:
        print(1)
        return
    if is_prime(d):
        print(2)
        return

    print(factors(d)+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions

def prime_divs(n):
    divs = {}
    for i in range(2, int(n**.5)+1):
        while n % i == 0:
            if i not in divs:
                divs[i] = 0
            divs[i] += 1
            n //= i
    if n != 1:
      if n not in divs:
      	divs[n] = 0
      divs[n] += 1
    return divs

  
A, B = map(int, input().split())
print(len(prime_divs(fractions.gcd(A, B))) + 1)

Submission status: Accepted

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


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


factors_a = factorize(a)
factors_b = factorize(b)

factors_a = {f[0] for f in factors_a}
factors_b = {f[0] for f in factors_b}

commons = factors_a & factors_b

print(len(commons) + 1)

Submission status: Accepted

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

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

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

    return arr
x=gcd(a,b)
if x!=1:
    print(len(factorization(x))+1)
else:
    print(1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
a, b = A, B
while b != 0:
  a, b = b, a % b
prod = 1
s = 1
p = 2
g = a
while a != 1:
  i = 0
  while a % p == 0:
    i += 1
    a //= p
    prod *= p
  if i != 0:
    s += 1
  p += 1
  if p > int(g**(1/2)) and prod != g:
    s += 1
    break
print(s)

Submission status: Accepted

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

import fractions

AB_gcd = fractions.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

c = make_divisors(AB_gcd)
c.sort()
for i, x in enumerate(c):
	if i == 0:
		continue
	if x == 0:
		continue
	for j in range(i+1,len(c)):
		if c[j] % x == 0:
			c[j] = 0

print(len([ans for ans in c if ans != 0]))

Submission status: Accepted

Solution code:
from fractions import gcd
 
def pf(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())
print(len(set(pf(gcd(a, b)))) + 1)

Submission status: Accepted

Solution code:
import fractions

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

import math
def prime_number(n):
    prime_list = []
    p = 2
    last = n

    while p <= math.sqrt(last)+1:
        cnt = 0
        if n % p != 0: pass
        else:
            while n % p == 0:
                n //= p
                cnt += 1

            prime_list.append((p, cnt))

        p += 1
    
    if n != 1: prime_list.append((p, cnt))
    return len(prime_list)

n = fractions.gcd(a, b)
print(prime_number(n) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd

def pf(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())
print(len(set(pf(gcd(a, b)))) + 1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
def gcd(a,b):
	if b == 0:
		return a
	else:
		return gcd(b,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

gcd = gcd(A,B)
p = set(prime_factorize(gcd))
print(len(p)+1)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
def gcd(a,b):
	if b == 0:
		return a
	else:
		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)
    return divisors
gcd = gcd(max(A,B),min(A,B))
divisors = sorted(make_divisors(gcd))
divisors.pop(0)
ans = [1]
while divisors:
    i = divisors.pop(0)
    for j in range(len(divisors)-1,-1,-1):
        if divisors[j]%i == 0:
            divisors.pop(j)
    ans.append(i)
print(len(ans))

Submission status: Accepted

Solution code:
# ----------------------------- #
def gcd(a, b):
    if a%b == 0:
        return b
    return gcd(b, a%b)

# ----------------------------- #
def is_prime_or_one(n):
    if n == 1: return True
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True

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

# ----------------------------- #
a, b = [int(_) for _ in input().split()]

GCD = gcd(a, b)  # 最大公約数
DV = make_divisors(GCD)  # 公約数

cnt = 0
for i in range(len(DV)):
    cnt += is_prime_or_one(DV[i])
print(cnt)

Submission status: Accepted

Solution code:
import fractions
a, b = map(int, input().split())
common_num = fractions.gcd(a, b)
 
ans = 1
for i in range(2,int(1+common_num**0.5)):
  if common_num % i == 0:
    ans += 1
    while common_num % i == 0:
      common_num //= i
if common_num > 1:
  ans += 1
      
print(ans)

Submission status: Accepted

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

print(len(set(prime_decomposition(n)))+1)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b = LI()
    g = fractions.gcd(a,b)
    s = set([1])
    while g % 2 == 0:
        s.add(2)
        g //= 2
    t = 3
    ss = int(g**0.5) + 1
    while g > t and t < ss:
        while g % t == 0:
            s.add(t)
            g //= t
        t += 2
    s.add(g)

    return len(s)


print(main())

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
import collections
a_list = collections.Counter(prime_factorize(a)).keys()
b_list = collections.Counter(prime_factorize(b)).keys()
ans = 0
for i in a_list:
    if i in b_list:
        ans+=1
print(ans+1) #1が入っていないから

Submission status: Accepted

Solution code:
# ABC142D - Disjoint Set of Common Divisors
def gcd(x: int, y: int) -> int:
    while y:
        x, y = y, x % y
    return x


def prime_factors(x: int) -> list:
    if x % 2:
        max_prime, factors = 0, []
    else:
        max_prime, factors = 2, [2]
        while x % 2 == 0:
            x //= 2
    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            factors.append(i)
            while x % i == 0:
                x //= i
    if x > 2:  # when x is prime greater than 2
        factors.append(x)
    return factors


def main():
    # compute the number of prime factors of gcd(A, B)
    A, B = map(int, input().split())
    g = gcd(A, B)
    ans = len(prime_factors(g)) + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = len(set(factor(a)) & set(factor(b))) + 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    x,y = map(int,input().split())
    tmp = [1]
    i = 2
    ans = 0
    # if x == y:
    #     ans += 1
    # a = factorization(x)
    # print(a)
    tempx = x

    for i in range(2, int(-(-x**0.5//1))+1):
        if tempx % i == 0:
            tmp.append(i)
            while tempx % i == 0:

                tempx //= i
    if tempx!=1:
        tmp.append(tempx)
    # print(tmp)

    for i,a in enumerate(tmp):
        if y % a == 0:
            tmp[i] = 1
        else:
            tmp[i] = 0
    print(sum(tmp))


if __name__=='__main__':
    main()

Submission status: Accepted

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

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

l = set(prime_d(a))
m = set(prime_d(b))

print(len(l&m)+1)

Submission status: Accepted

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

def f(n):
    r = []
    import math
    max_i = int(math.sqrt(n))
    for i in range(2, max_i + 1):
        while n % i == 0:
            n /= i
            r.append(i)
    if n != 1:
        r.append(n)
    return r
    

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

a_and_b = a & b
# print(a_and_b)
print(len(a_and_b) + 1)

Submission status: Accepted

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

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

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

a_and_b = a & b
# print(a_and_b)
print(len(a_and_b) + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

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

def hurui(n):
    is_prime = [0] * (n+10)
    for i in range(2, n+1):
        is_prime[i] = 1
    for i in range(2, n+1):
        if is_prime[i] == 1:
            j = i*2
            while j <= n:
                is_prime[j] = 0
                j += i
    return is_prime

def main():
    a, b = list(map(int, input().strip().split()))
    g = gcd(a, b)
    # is_prime = hurui(10**6+10)
    i = 2
    c = 0
    # print(g)
    ans = []
    while i**2 <= g:
        if g % i == 0:
            ans.append([i, 0])
            while g % i == 0:
                g /= i
                ans[-1][1] += 1
        i += 1
    if g != 1:
        ans.append([g, 1])
    # print(ans)
    print(len(ans)+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

bb = int((b ** 0.5) // 1)

ans = 0
for i in range(1,bb+1):
    n = []
    m = []
    if a % i == 0 and b % i == 0:
        ii = int((i ** 0.5) // 1)
        m.append(i)
        n.append(ii)
    if b % i == 0 and a % (b // i) == 0 and b % (b // i) == 0 and b != 1:
        ii = int(((b // i) ** 0.5) // 1)
        m.append(b // i)
        n.append(ii)
    for j in range(len(n)):
        s = 1
        for k in range(2, n[j]+1):
            if m[j] % k == 0:
                s = 0
                break
        if s == 1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
A,B=map(int,input().split())
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
p=prime_factorize(gcd(A,B))
if len(p)==0:
    print(1)
    exit()
cnt=1
#print(p)
for i in range(1,len(p)):
    if p[i]!=p[i-1]:
        cnt+=1
print(cnt+1)

Submission status: Accepted

Solution code:
# ABC-142-D
A, B = map(int, input().split())
ans = 1

#最大公約数
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def factorize(x):
    factor = []
    for num in range(2, int(x**0.5)+1):
        while x % num == 0:
            x //= num
            factor.append(num)
    if x != 1:
        factor.append(x)
    return set(factor)
    
gcd_AB = gcd(A, B)
prime = factorize(gcd_AB)
ans += len(prime)
print(ans)

Submission status: Accepted

Solution code:
import fractions
import random


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


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

ans = 1
for divisor in divisors:
    if is_prime3(divisor):
        ans += 1

print(ans)

Submission status: Accepted

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

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

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


# https://en.wikipedia.org/wiki/Trial_division
def f(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)
    # Only odd number is possible
    return a


c = gcd(A, B)

print(len(set(f(c))) + 1)

Submission status: Accepted

Solution code:
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


def gcd(h, l):
    if h % l:
        return gcd(l, h % l)
    else:
        return l


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque
from math import sqrt
#https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b?lang=en
#B - Counting of Trees
"""
sort, and then check how many next levels we have against the previes level
keep a prevcount, and each level is prev level ** cur elvel
"""
A = gi()
B = gi()

div = gcd(max(A, B), min(A, B))

ans = 1
cur = div
for d in range(2, int(sqrt(div)) + 1):
    if (cur == 1):
        break
    if cur % d == 0:
        ans += 1
    while cur % d == 0:
        cur = cur // d

#    print(cur, d)

if cur > 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

A, B = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

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

# https://en.wikipedia.org/wiki/Trial_division
def f(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)
    # Only odd number is possible
    return a

c = gcd(A, B)

print(len(set(f(c))) + 1)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def integer_factorization(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[n] += 1
    return prime_count

prime = [True] * (10**6 + 2)
prime[1] = False
max_range = int(math.sqrt(10**6)) + 1

for i in range(2, 10**6 + 1):
    if not prime[i]:
        continue
    if prime[i]:
        num = i + i
        while num < max_range:
            prime[num] = False
            num += i

def main():
    gcd = fractions.gcd
    A, B = LI()
    m = gcd(A, B)
    cnt = 1
    cnt += len(integer_factorization(m))
    # for i in range(2, int(math.sqrt(m)) + 1):
    #     if m % i != 0:
    #         continue
    #     if prime[i]:
    #         cnt += 1
    print(cnt)
main()