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: Wrong Answer

Solution code:
A, B = [int(s) for s in input().split()]
def gcd(x, y):
  while y != 0:
    x, y = y, x%y
  return x
def divisors(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

gcd_divisors = divisors(gcd(A, B))
N = len(gcd_divisors)
count = 0
for i in range(N):
  flg = False
  for j in range(N-1-i-1):
    if gcd(gcd_divisors[N-1-i], gcd_divisors[j]) != 1:
      flg = True
      break
  if flg == False:
    count += 1
print(count)

Submission status: Wrong Answer

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

# LL = 10
# dp = [[-1 for x in range(LL)] for _ in range(LL)]
# dp2 = [[0 for x in range(LL)] for _ in range(LL)]

def gcd(a, b):
    if b == 0:
        return a
    else:
        if dp[a][b] == -1:
            gcd(b, a%b)
        else:
            return dp[a][b]

def is_disjoint(a, b):
    if a < b:
        tmp = b
        b = a
        a = tmp
    d = a % b
    if d != 0 and b % d == 1:
        return True
    else:
        return False

def get_common_divisors(a, b):

    dvs = set()

    n = 0
    d = 0
    if (a>b):
        d = a - b
        n = a
    else:
        d = b-a
        n = b

    i = 1
    while i <= math.sqrt(d): 
        if (d % i == 0 and a%i == 0 and b%i == 0):
            if (d // i == i) : 
                dvs.add(i)
            else: 
                dvs.add(i)
                dvs.add(d//i)
        i = i + 1
    
    return dvs

def get_divisors(n) : 

    dvs = set()
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n // i == i) : 
                dvs.add(i)
            else : 
                dvs.add(i)
                dvs.add(n//i)
        i = i + 1
    
    return dvs



As = get_divisors(A)
print(As)
Bs = get_divisors(B)
print(Bs)
CDL = list(As & Bs)
print(CDL)

CDLL = len(CDL)
print(CDLL)

num = 0
min_num = 1e15

for i in range(0, CDLL):
    num = 0
    for j in range(i, CDLL):
        if is_disjoint(CDL[i], CDL[j]):
            # dp[CDL[i]][CDL[j]] = 1
            # dp[CDL[j]][CDL[i]] = 1
            num += 1
    if min_num > num:
        min_num = num

print(min_num + 1)


# for l in range(len(CDL)+1):
#     dp2[1][l] = 1

# for l in range(2, len(CDL)+1):
#     for p in range(l, len(CDL)+1):
#         if dp[CDL[l]][CDL[p]] == 1:
#             pass

Submission status: Wrong Answer

Solution code:
# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数を２つのグループに分ける

from collections import defaultdict
import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = defaultdict(lambda : 0)
  #print(c)
  fac[1] = 1
  fac = facto(c, fac)
  #print(fac)
  keys = list((fac.keys()))
  print(len(keys))  
  
def facto(n, fac):
  if n == 1:
    return fac
  # cursor = 2
  sosu = calcSosu(int(n ** 0.5))
  for cursor in sosu:
    if n % cursor == 0:
      fac[cursor] += 1
      n = n // cursor
      if n == 1:
        break
    else:
      cursor += 1
      
  return fac

def calcSosu(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
  
  
def gojo(a,b):
  if b > a:
    a, b = b, a
  c = a % b
  if c == 0:
    return(b)
  else:
    return gojo(b, c)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import math
a,b = map(int,input().split())
d = []
j = 1
if a>=b:
  x = a
else:
  x = b
for i in range (1,x):
  if a%i==0 and b%i==0:
    d+=[i]
while j<len(d):
  k=j+1
  while k<len(d) and d[k]<math.sqrt(d[len(d)-1]):
    if d[k]%d[j]==0:
      d.pop(k)
      k-=1
    else:
      k+=1
  j+=1
print(len(d))

Submission status: Wrong Answer

Solution code:
import math

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

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

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

    return True

cf=[]
for i in range(1,int(math.sqrt(max(A,B)))+1):
    if A % i == 0 and B % i == 0:
        if is_prime(i):
            cf.append(i)

print(len(cf))

Submission status: Wrong Answer

Solution code:
A,B=map(int,input().split())
arr=set()
X=max(A,B)
if X>3:
    for i in range(1,int(X**0.5)+1):
        if A%i==0 and B%i==0:
            arr.add(i)
    s=min(arr);e=max(arr)
    def make_divisors(n,s,e):
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if i!=s and i!=e:
                if n % i == 0 :
                    divisors.add(i)
                    if i != n // i:
                        divisors.add(n//i)
        return divisors
    cnt=0
    for j in arr:
        if len(make_divisors(j,0,0) & arr)<3:
            cnt+=1
    print(cnt)
elif X==1:
    print(0)
elif X==3 and min(A,B)==2:
    print(0)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
# D - Disjoint Set of Common Divisors
A, B = map(int, input().split())

d = int(min(A, B)**0.5)

tmp = 0
DP =[1]
if A % 2 == 0 and B % 2 == 0:
    DP.append(2)

for i in range(3,d+1):
    if A % i == 0 and B % i == 0:
        tmp = 0
        for j in range(1,len(DP)):
            if i % DP[j] == 0:
                tmp = 0
                break
            else:
                tmp = 1
        if tmp == 1:
            DP.append(i)


    else:
        pass

print(len(DP))

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
i = 2
cnt = 0
tmpA, tmpB = A, B
while i**2 <= min(tmpA, tmpB) and i <= min(A,B):
    if A % i == 0 and B % i == 0:
        cnt += 1
        while A % i == 0 and B % i == 0:
            A //= i
            B //= i
    i += 1
if cnt == 0 and min(A, B) != 1:
    cnt += 1
print(cnt + 1)

Submission status: Wrong Answer

Solution code:
import math

divisor=[1]
#eiclidean algorithm
A,B=map(int,input().split())
p=max(A,B)
q=min(A,B)
int2=0
gcd=0
while True:
    int2=p%q
    if int2==0:
        gcd=p//q
        break
    else:
        p=q
        q=int2

if gcd%2==0:
    divisor+=[2]

for i in range(3,math.ceil(math.sqrt(gcd))+1):
    if gcd%i==0:
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

print(len(divisor))

Submission status: Wrong Answer

Solution code:
import fractions
import math

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

#limit = fractions.gcd(a, b)
limit = min(int(math.sqrt(a)), int(math.sqrt(b)))
cnt = 0
for i in range(2, limit+1):
  flag = False
  while (a % i == 0) and (b % i == 0):
    a = a // i
    b = b // i
    flag = True
  if flag:
    cnt += 1

last = min(a, b)
flag = False
if (a % last == 0) and (b % last == 0):
  cnt += 1

   
print (cnt+1)

Submission status: Wrong Answer

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

factor = []
max_iter = int(math.sqrt(greatest)) + 2
for i in range(2, max_iter):
    while greatest % i == 0:
        greatest //= i
        factor.append(i)
factor = set(factor)
print(len(factor) + 1)