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:
def divisor(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


def common_divisor(a, b):
    table = []
    for i in a:
        if i in b:
            table.append(i)
    return table


def resolve():
    A, B = map(int, input().split())
    a_list = divisor(A)
    b_list = divisor(B)
    common_list = common_divisor(a_list, b_list) if len(a_list) < len(b_list) else common_divisor(b_list, a_list)
    common_list.sort()
    print(common_list)
    i = 1
    while i < len(common_list):
        j = i + 1
        while j < len(common_list):
            if common_list[j] % common_list[i] == 0:
                del common_list[j]
            else:
                j += 1
        i += 1

    print(len(common_list))
    
resolve()

Submission status: Wrong Answer

Solution code:
def divisor(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


def common_divisor(a, b):
    table = []
    for i in a:
        if i in b:
            table.append(i)
    return table


def resolve():
    A, B = map(int, input().split())
    a_list = divisor(A)
    b_list = divisor(B)
    common_list = common_divisor(a_list, b_list) if len(a_list) < len(b_list) else common_divisor(b_list, a_list)

    i = 1
    while i < len(common_list):
        j = i + 1
        while j < len(common_list):
            if common_list[j] % common_list[i] == 0:
                del common_list[j]
            else:
                j += 1
        i += 1

    print(len(common_list))
    
resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
N=list(map(int,input().split()))
A,B=max(N),min(N)
#ユーグリッド
GCD=1
while True:
    r=A%B
    if r==0:
        GCD=B
        break
    else:
        A=B
        B=r

_GCD=int(np.sqrt(GCD))
num_list=np.arange(1,_GCD+1)
count=0
ans_list=np.array([])
#1から調べていき、逐一倍数をリストから消していく
while not list(num_list) == [] :
    num=num_list[0]
    if A%num==0 and B%num==0:
        count+=1
        if num==1:
            num_list=num_list[~(num_list==1)]
        else:
            ans_list=np.append(ans_list,num)
            num_list=num_list[~(num_list % num == 0)]
    else:
        num_list=num_list[~(num_list % num == 0)]
        
num_list= 6/ans_list

while not list(num_list) == [] :
    num=num_list[0]
    if A%num==0 and B%num==0:
        count+=1
        if num==1:
            num_list=num_list[~(num_list==1)]
        else:
            num_list=num_list[~(num_list % num == 0)]
    else:
        num_list=num_list[~(num_list % num == 0)]

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=list(map(int,input().split()))
A,B=max(N),min(N)
#ユーグリッド
GCD=1
while True:
    r=A%B
    if r==0:
        GCD=B
        break
    else:
        A=B
        B=r

_GCD=int(np.sqrt(GCD))
num_list=np.arange(1,_GCD+1)
count=0
ans_list=np.array([])
#1から調べていき、逐一倍数をリストから消していく
while not list(num_list) == [] :
    num=num_list[0]
    if A%num==0 and B%num==0:
        count+=1
        ans_list=np.append(ans_list,num)
        if num==1:
            num_list=num_list[~(num_list==1)]
        else:
            num_list=num_list[~(num_list % num == 0)]
    else:
        num_list=num_list[~(num_list % num == 0)]
        
num_list= 6/ans_list

while not list(num_list) == [] :
    num=num_list[0]
    if A%num==0 and B%num==0:
        count+=1
        if num==1:
            num_list=num_list[~(num_list==1)]
        else:
            num_list=num_list[~(num_list % num == 0)]
    else:
        num_list=num_list[~(num_list % num == 0)]

print(count)

Submission status: Wrong Answer

Solution code:
import collections


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

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

def tameshiwari(n):
  result=[]

  f=2
  if n==2:
    result.append(2)
  while f*f<n:
    if n%f==0:
      result.append(f)
      n=n//f
    else:
      f+=1
  if n!=1:
    result.append(n)
  return result
  

c = collections.Counter(tameshiwari(gcd(a,b)))
print(len(c)+1)

Submission status: Wrong Answer

Solution code:
import collections


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

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

def tameshiwari(n):
  result=[]

  f=2
  while f*f<n:
    if n%f==0:
      result.append(f)
      n=n//f
    else:
      f+=1
  if n!=1:
    result.append(n)
  return result
  

c = collections.Counter(tameshiwari(gcd(a,b)))
print(len(c)+1)

Submission status: Wrong Answer

Solution code:
import collections


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

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

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

c = collections.Counter(tameshiwari(gcd(a,b)))
print(len(c)+1)

Submission status: Wrong Answer

Solution code:
import collections


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

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

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

c = collections.Counter(tameshiwari(gcd(a,b)))
print(len(c)+1)

Submission status: Wrong Answer

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

#最大公約数xを求める
x,y = max(a,b),min(a,b)
while y!=0:
    x,y = y,x%y

#Xを素因数分解する
tmp = x
Factoring = [1]
if x > 1:
    for i in range(2,x//2+1):
        if x%i==0:
            Factoring.append(i)
            while tmp % i == 0:
                tmp = tmp//i
            x = tmp
print(len(Factoring))

Submission status: Wrong Answer

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

#最大公約数xを求める
x,y = max(a,b),min(a,b)
while y!=0:
    x,y = y,x%y

#Xを素因数分解する
tmp = x
Factoring = [1]
if x > 1:
    for i in range(2,x):
        if x%i==0:
            Factoring.append(i)
            while tmp % i == 0:
                tmp = tmp//i
            x = tmp
print(len(Factoring))

Submission status: Wrong Answer

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


sqA = int(math.sqrt(A)+2)
sqB = int(math.sqrt(B)+2)

A_candidate = set()
B_candidate = set()


for i in range(1,sqA): 
    while A%i == 0:
        A = A//i
        A_candidate.add(i)
        if i == 1:
            break
for i in range(1,sqB):
    while B%i == 0:
        B = B//i
        B_candidate.add(i)
        if i == 1:
            break
print(len(A_candidate.intersection(B_candidate)))

Submission status: Wrong Answer

Solution code:
import math

a, b = map(int, input().split())
k = []
for i in range(2, min(a, b)+1):
    if a % i == 0 and b % i == 0:
        k.append(i)
cnt = 1
for n in k:
    flg = "composite"
    for p in range(2, n):
        if n == 2:
            cnt += 1
        elif n % p == 0:
            break
        else:
            flg = "prime"
    if flg == "prime":
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import fractions

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

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

f = gcd(A, B)

kouyakusuu = []
for i in range(2, int(-(-f**0.5//1))+1):
    # print(f, i)
    if f % i != 0:
        continue
    else:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
    if f == 1:
        break
# print(kouyakusuu)
print(len(kouyakusuu)+1)

Submission status: Wrong Answer

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

def prime(n):
    is_prime=[True]*(n+1)
    is_prime[0],is_prime[1]=False,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
    prime_num=[i for i in range(n+1) if is_prime[i]]
    return prime_num

p=min(a,b)
count=1
for i in prime(10**6):
    if p<i or 10**6<i:break
    elif a%i==0 and b%i==0:
        count +=1
print(count)

Submission status: Wrong Answer

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


sqA = int(math.sqrt(A)+1)
sqB = int(math.sqrt(B)+1)

A_candidate = set()
B_candidate = set()
A_candidate.add(A)
B_candidate.add(B)

for i in range(1,sqA): 
    while not A%i:
        A /= i
        A_candidate.add(i)
        if i == 1:
            break
for i in range(1,sqB):
    while not B%i:
        B /= i
        B_candidate.add(i)
        if i == 1:
            break

print(len(A_candidate.intersection(B_candidate)))

Submission status: Wrong Answer

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


sqA = int(math.sqrt(A)+1)
sqB = int(math.sqrt(B)+1)

A_candidate = set()
B_candidate = set()

for i in range(1,sqA): 
    while not A%i:
        A /= i
        A_candidate.add(i)
        if i == 1:
            break
for i in range(1,sqB):
    while not B%i:
        B /= i
        B_candidate.add(i)
        if i == 1:
            break

print(len(A_candidate.intersection(B_candidate)))

Submission status: Wrong Answer

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

def fact(n):
    b = 2
    li = []
    li.insert(0,1)
    while b*b<=n:
        while n%b == 0:
            n = n//b
            li.append(b)
        b+=1
    if n>1:
        li.append(n)

    return li
a,b = map(int,input().split())
c = gcd(a,b)
print(len(fact(c)))

Submission status: Wrong Answer

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

n=10**6
is_prime=[True]*(n+1)
is_prime[0],is_prime[1]=False,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
prime=[i for i in range(n+1) if is_prime[i]]

p=min(a,b)
count=1
for i in prime:
    if p<i:break
    elif a%i==0 and b%i==0:
        count +=1

print(count)

Submission status: Wrong Answer

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

n=10**6
is_prime=[True]*(n+1)
is_prime[0],is_prime[1]=False,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
prime=[i for i in range(n+1) if is_prime[i]]

min_n=(min(a,b)//2)+1
count=1
for i in prime:
    if min_n<i:break
    elif a%i==0 and b%i==0:
        count +=1

print(count)