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: Time Limit Exceeded

Solution code:
import math
import fractions
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_prime(num):
    for i in range(2, num):  # 第二引数は sqrt(num)+1 でも良い
        if num % i == 0:
            return False

    return True

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

g = fractions.gcd(A, B)

div = make_divisors(g)
ans = 0
for i in div:
    if is_prime(i):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import fractions

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

g=fractions.gcd(A,B)

if g==1:
    print(1)
    exit()
cnt=0
for i in range(2,g+1):
    if g%i==0:
        cnt+=1
        g=g//i
        while g%i==0:
            g=g//i
print(cnt+1)

Submission status: Time Limit Exceeded

Solution code:
# 190928 D
from fractions import gcd

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
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

A,B = list(map(int,input().split()))
koyaku = gcd(A,B)
kotable = sorted(divisor(koyaku))
isprim, solist = sieve(koyaku)
output = []
for i in range(len(kotable)):
    if kotable[i] in solist:
        output.append(kotable[i])

print(len(output)+1)

Submission status: Time Limit Exceeded

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

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
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

A,B = list(map(int,input().split()))
koyaku = gcd(A,B)
kotable = sorted(divisor(koyaku))
isprim, solist = sieve(koyaku)
output = []
for i in range(len(kotable)):
    if kotable[i] in solist:
        output.append(kotable[i])

print(len(output)+1)

Submission status: Time Limit Exceeded

Solution code:
num_line=input().rstrip().split(" ")
numA=int(num_line[0])
numB=int(num_line[1])

if(numA>=numB):
    NumMin=numB
    NumMax=numA
else:
    NumMin=numA
    NumMax=numB

lst_p=[]
import math

for i in range(NumMin):
    if NumMin%(i+1)==0:
        lst_p.append(i+1)
        
#print(lst_p)

lst2_p=[]
for i in range(len(lst_p)):
    lst2_p.append(lst_p[i])
    if NumMax%(lst_p[i])!=0:
        lst2_p.remove(lst_p[i])
#print(lst2_p)

lst3_p=[]
for i in range(len(lst2_p)):
    lst3_p.append(lst2_p[i])
    s=0
    for j in range(1,i):
        if lst2_p[i]%(lst2_p[j])==0:
            s+=1
    if s!=0:
        lst3_p.remove(lst2_p[i])
            

print(len(lst3_p))
#print(lst3_p)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
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
y = sorted(make_divisors(gcd(a,b)))
r = []
for i in y[1:]:
    y_y = make_divisors(i)
    f = True
    for j in y_y:
        if j in r:
            f = False
            break
    if f:
        r.append(i)
print(len(r)+1)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b = list(map(int,input().split()))
cf=[]
ccf=[]
for i in range(2,min(a,b)+1):
  if a % i == 0 and b % i == 0:
    cf.append(i)
for ii in range (len(cf)):
  q=0
  if cf[ii] == 1: 
    q =1
  for k in range(2, int(math.sqrt(cf[ii])) + 1):
    if cf[ii] % k == 0:
      q=1
  if q ==0:
    ccf.append(cf[ii])
print(len(ccf)+1)

Submission status: Time Limit Exceeded

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


a = make_divisors(A)
b = make_divisors(B)
L = []
for x in a:
    if x in b:
        L.append(x)

ans = 0
for l in L:
    flag = False
    for i in range(2, l):
        if l % i == 0:
            flag = True
            break
    if flag:
        continue
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

def cf(x1,x2):
    gcd_num = gcd(x1,x2)
    ret = range(2, gcd_num+1)
    for y in [2, 3, 5, 7, 11, 13, 17]:
        if y in ret:
            ret = [x for x in ret if x % y != 0]
            ret.append(y)
    cf=[1]
    for i in ret:
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf


inputData = input().split()
A, B = [int(x) for x in inputData]
cd = cf(A, B)
ans = set(cd)
list_len_dyn = len(cd)
for i in range(1, len(cd) + 1):
    if i == list_len_dyn:
        break
    to_be_removed = []
    for j in range(i + 1, len(cd)):
        if cd[j] % cd[i] == 0:
            to_be_removed.append(cd[j])
            continue
        if gcd(cd[i], cd[j]) != 1:
            to_be_removed.append(cd[j])
    for k in to_be_removed:
        cd.remove(k)
    list_len_dyn = len(cd)
print(len(cd))