Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Accepted

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

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

def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    if n < 2:
        return [1]
    prime_factors = [1]
    n_prime_lim = int(n**0.5) + 1
    for p in range(2, n_prime_lim):
        if p*p > n:
            break
        if n % p == 0:
            prime_factors.append(p)
        while n % p == 0:
            n //= p
    if n > 1:
        prime_factors.append(n)
    return prime_factors

gcd_ab = gcd(A, B)
prime_factors = trial_division(gcd_ab)
print(len(prime_factors))

Submission status: Accepted

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

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
     
A_div = divisor(A)
B_div = divisor(B) 
common_div = list(set(A_div) & set(B_div))
common_div.sort()

for i in common_div:
  tmp = [1 for j in answer[1:] if i % j == 0]
  if len(tmp) == 0:
    answer.append(i)
    
print(len(answer))

Submission status: Accepted

Solution code:
import math

#関数gcd(a,b):最大公約数を求め、返す。a>b(どちらも整数）が前提
def gcd(a,b):
   if a%b==0:
       return b
   else:
        return gcd(b,a%b)

#A,B:与えられる正整数
A,B=map(int,input().split())

#MD:AとBの最大公約数
if A>=B:
    MD=gcd(A,B)
else:
    MD=gcd(B,A)

#count:求める個数（「１」があるため初めから１が入っている）
count=1
    
#MDの約数の中で素数のみをカウント(2以上、√MD以下の数）
for i in range(2,int(math.sqrt(MD))+1):
    if MD%i==0:
        count+=1
        while MD%i==0:
            MD=MD/i
    else:
        pass
#MDの約数の中で√MDより大きい素数は高々一つだからその確認
if MD!=1:
    count+=1
else:
    pass
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


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


def main():
    A, B = [int(e) for e in inp().split()]

    G = gcd(A, B)

    ans = 1
    v = G
    p = 2
    while p * p <= v:
        if v % p == 0:
            ans += 1
            v //= p
            while v % p == 0:
                v //= p
        p += 1

    if v > 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
def prime_factorize_2(n):
    res = set()
    div = 2
    if n % 2 == 0:
        while n % div == 0:
            n //= div
        res.add(div)
    div += 1
    while div ** 2 <= n:
        if n % div == 0:
            n //= div
            res.add(div)
        else:
            div += 2
    if n != 1:
        res.add(n)
    return res

def main(a, b):
    #a, b = [int(i) for i in sys.stdin.readline().split()]
    _gcd = gcd(a,b)
    #memo_ls = [0 for i in range(_gcd)]
    #memo_set = set()
    cnt = 0
    if _gcd == 1:
        print(1)
    else:
        res = prime_factorize_2(_gcd)
        print(len(res) + 1)
if __name__ == "__main__":
    a, b = [int(i) for i in sys.stdin.readline().split()]
    main(a, b)

Submission status: Accepted

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

def coprime(a, b):
    return gcd(a, b) == 1

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())
if (A==1)or(B==1)or(coprime(A,B)):
  print(1)
else:
  A=make_divisors(A)
  B=make_divisors(B)
  C=list(set(A)&set(B))
  C.sort(reverse=True)
  count=0
  for i in range(len(C)):
    for j in range(i+1,len(C)):
      if (C[j]!=1)and(C[i]%C[j]==0):
        count=count+1
        break
  print(len(C)-count)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

def main(a, b):
    #a, b = [int(i) for i in sys.stdin.readline().split()]
    _gcd = gcd(a,b)
    #memo_ls = [0 for i in range(_gcd)]
    #memo_set = set()
    cnt = 0
    if _gcd == 1:
        print(1)
    else:
        res = prime_factorize(_gcd)
        print(len(res) + 1)
if __name__ == "__main__":
    a, b = [int(i) for i in sys.stdin.readline().split()]
    main(a, b)

Submission status: Accepted

Solution code:
import collections

x, y = map(int, input().split())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
z=gcd(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
print(len(collections.Counter(prime_factorize(z))) +1 )

Submission status: Accepted

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

GCD = fractions.gcd(A,B)

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

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

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

    return arr

l = factorization(GCD)
if len(l) == 1 and l[0][0] == 1:
    print(len(l))
else:
    print(len(l)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
A,B = map(int, input().split())
g=gcd(A,B)
def prime_factorization(n):
    prime_num = []
    for i in range(2, int(n**.5)+1):
        num = 0
        while True:
            x,y = divmod(n, i)
            if y!= 0:
                break
            n = x
            num += 1
        if num>0:
            prime_num.append(i)
    if n > 1:
        prime_num.append(n)
    return prime_num
print(len(prime_factorization(g))+1)

Submission status: Accepted

Solution code:
from fractions import gcd
A,B=map(int,input().split())
s=set()
x=gcd(A,B)
y=2
while y*y<=x:
  while x%y==0:
    s.add(y)
    x//=y
  y+=1
if x>1:
  s.add(x)
print(len(s)+1)

Submission status: Accepted

Solution code:
from fractions import*
n=gcd(*map(int,input().split()))
a=i=1
while i*i<n:
 	i+=1;a+=n%i<1
 	while n%i<1:n/=i
print(a+(n>1))

Submission status: Accepted

Solution code:
def trial_division(n):
    a = [1]
    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 gcd(x, y):
    if x > y:
        return gcd(y, x)
    # x <= y
    temp = y % x
    if temp == 0:
        return x
    else:
        return gcd(temp, x)


def main():
    a, b = map(int, input().split())
    gcd_ab = gcd(a, b)
    temp_list = trial_division(gcd_ab)
    # print(gcd_ab)
    # print(temp_list)
    temp_set = set(temp_list)
    print(len(temp_set))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
GCD(A, B) の公約数を素因数分解して出てきた素数の数+1 が答え.
"""

import math
from fractions import gcd  # gcd: 2つの正の数を渡すと最大公約数(Greatest Common Divisor)を返す  # Atcoder ではこっち
from collections import OrderedDict


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

# A, B の公約数 = gcd(a, b)の公約数
# GCD
gcd_num = gcd(a, b)

# 素因数分解
"""
N = p * q    (p <= q, pとqは素因数) の時
p <= sqrt(N)    となる

つまり, sqrt(N) まで試して, 割り切れなかった(残った)ものは素因数と言える.
言い方を変えると, sqrt(N)以上の素因数は高々1個まで.

これから, 順番に割っていくのをsqrt(N)までやり, 残ったのが1じゃなければそれも素数.
これなら計算量 O(sqrt(N)) でいける.
"""
def factorize(n):
    """素因数分解を行う

    Parameters
    ----------
    n : int
        正の自然数
    """
    res = dict()
    for i in range(2, math.ceil(math.sqrt(n))):
        if n%i:  # 割り切れなかったらcontinue
            continue
        res[i] = 0
        while (n%i == 0):
            n /= i
            res[i] += 1

    if (n != 1):
        res[n] = 1
    return res


res = factorize(gcd_num)
ans = len(res.keys()) + 1  # 1は必ず入る
print(ans)