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:
a,b = map(int,input().split())
if min(a,b) <=2:
    if max(a,b) % 2 !=0:
        print(1)
        exit()
    else:
        print(2)
        exit()

comm = [1,2]
end = int(((max(a,b)) + 1)/2) + 1
if end >= min(a,b):
    end = min(a,b)+1

for i in range(3,end,2):
    if a % i ==0 and b % i == 0:
        flag1 = True
        for j in comm[1:]:
            if i <= j:
                flag1 = False
                break
            if i % j == 0:
                flag1 = False
                break
        if flag1:
            comm.append(i)

print(len(comm))

Submission status: Time Limit Exceeded

Solution code:
import fractions


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

g = fractions.gcd(A, B)

ya = []
for i in range(2, g+1):
    if g % i == 0:
        f = 0
        k = [1 for y in ya if i % y==0]
        if len(k) == 0:
            ya.append(i)


print(len(ya) + 1)

Submission status: Time Limit Exceeded

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

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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 = cf(A, B)
ch = c[1:]
t =[1]
for i in ch:
    d = make_divisors(i)
    d.pop()
    d.pop(0)
    leng = len(set(d)-set(ch))
    if len(d) == leng:
        t.append(i)
ans=len(t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
if B>A:
   m=B
   B=A
   A=m
while B!=0:
    A,B=B,A%B
large=A
ans=[]
for i in range(2,large+1): 
  if len(ans)>=1:
    if large%i==0: 
        count=0
        for k in ans:
            a=i%k
            if a!=0:
                count+=1
        if count==len(ans):
            ans.append(i)                
  else:
    if large%i==0:
      ans.append(i)

print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math

def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  if n % 2 == 0:
    # ２ではない偶数は素数ではない
    return False
  
  # nの半分まで計算する範囲を絞る
  m = math.floor(n / 2) + 1
  for p in range(3, m, 2): # 奇数だけ計算する
      if n % p == 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=map(int, input().split()) 

a_d = set(make_divisors(a))
b_d = set(make_divisors(b))
lists = list(a_d & b_d)
res = 1
for i in lists:
    if isPrime(i):
        res +=1
print(res)

Submission status: Time Limit Exceeded

Solution code:
A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= {1}
    tmp = n

    for i in range(2,int(n/2)+1):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)

    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[]:
        sosu.add[n]
    
    return sosu

ans = len(bunkai(A)&bunkai(B))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    primeNum.append(1)
    return primeNum

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[-1][0]

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = factorization(N)
    pl = seachPrimeNum(ms)
    ans=0
    for i in range(len(pl)):
        if N%pl[i]==0:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

a,b = map(int,input().split())
n = fractions.gcd(a,b)
if n ==1:
    print(1)
else:
    l = [1]
    for i in range(n):
        if n%(i+2)==0:
            l.append(i+2)
            while n%(i+2)==0:
              n = n//(i+2)
        if i>n-1:
            break
    print(len(l))

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
arr=set()
X=min(A,B)
for i in range(1,(X+1)//2+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)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

def prime_enemerate(A):
    a=[i for i in range(5,A+1) if i%2!=0 and i%3!=0]
    a_judge=[i for i in range(5,int(math.sqrt(A))+1) if i%2!=0 and i%3!=0]

    while len(a_judge)!=0:
        a0=a_judge[0]
        a=[i for i in a if i%a0!=0 or i==a0]
        a_judge=[i for i in a_judge if i%a0!=0]

    return [2,3]+a

A,B=map(int,input().split())
judge_max=fractions.gcd(A,B)
prime=prime_enemerate(judge_max)
result=0

for i in prime:
    if A%i==0 and B%i==0:
        result+=1

print(result+1)

Submission status: Time Limit Exceeded

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

n = 2

while n <= max(a, b):
    if a%n == 0 and b%n == 0:
        while a%n == 0:
            a = a//n
        while b%n == 0:
            b = b//n
        ans += 1
    
    n += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            if prime(i):
                cf.append(i)
    return cf


def main():
    A, B = map(int,input().split())
    V = len(cf(A,B))
    if V == 0:
        print(1)
    else:
        print(V+1)

    
if __name__ == '__main__':
    main()

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

d_list=[]
for i in range(1,g+1):
    if g%i==0:
        d_list.append(i)


if len(d_list)==2:
    print(2)
    exit()

i=1

while d_list[i]<g:
    j=2
    temp=d_list[i]
    while temp*j<=d_list[-1]:
        if temp*j in d_list:
            d_list.remove(temp*j)
        j+=1
    i+=1
    if i==len(d_list):
        break


print(len(d_list))