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:
# coding: utf-8

import heapq

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
    
A, B = map(int,input().split())
array = cf(A, B)
heapq.heapify(array)
A = []
tmp = 0

for i in range(len(array)):
    tmp = heapq.heappop(array)
    if A == []:
        A.append(tmp)
    else:
        for i in range(len(A)):
            if tmp % A[i] == 0:
                break
            else:
                if i == len(A) - 1:
                    A.append(tmp)
    if array == []:
        break
print(len(A) + 1)

Submission status: Time Limit Exceeded

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

def DSoCD(a, b):
    result = []
    cd_list = [x for x in range(1,min(a,b)+1) if a%x == 0 and b%x == 0]
    for idx,n in enumerate(cd_list):
        t = list(filter(lambda x: n%x == 0, cd_list[0:idx+1]))
        if len(t) < 3:
            result.append(n)
    return len(result)

if __name__ == "__main__":
    [A, B] = list(map(int,input().split()))
    print(DSoCD(A,B))

Submission status: Time Limit Exceeded

Solution code:
A,B=input().split()
a=int(A)
b=int(B)
m=1
n=1
while n<=min(a,b):
  if a%n==0:
    if b%n==0:
      m=n
      n=n+1
    else:
      n=n+1
  else:
    n=n+1
if m==1:
  print(1)
elif m==2:
  print(2)
else:
  x=3
  u=0
  v=0
  while x<=m:
    t=2
    while t<=x-1:
      if x%t==0:
        u=u+1
        t=t+1
      else:
        u=u
        t=t+1
    if u==0:
      if m%x==0:
        v=v+1
    u=0
    x=x+1
  print(v+2)

Submission status: Time Limit Exceeded

Solution code:

from sys import stdin
import math

a,b = [int(x) for x in stdin.readline().rstrip().split()]
 
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
 
if a == 1:
    print(1)
    exit()
 
def cf(x1,x2):
    cf=[]
    cf.append(1)
    k = min(x1,x2)
    for i in range(2,k+1):
        if is_prime(i) == True:
            if x1 % i == 0 and x2 % i == 0:
                cf.append(i)
    return len(cf)
 
print(cf(a,b))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
a, b = map(int, input().split())
if a < b:
    small = a
else:
    small = b
list = []
for i in range(1, small):
    if a % i == 0:
        if b % i == 0:
            list.append(i)
length = len(list)
for len_i in range(0, length):
    for len_j in range(1, length-len_i-1):
        if list[length-len_i-1] % list[len_j] == 0:
            list.pop(length-len_i-1)
            break
ans = len(list)
if ans == 0:
    ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def euc(a,b):
  if a<b:
    a,b=b,a
  while(a%b!=0):
    a,b=b,a%b
  return b
 
one,two = [int(x) for x in input().split()]
 
aa = euc(one,two)
 
c=[]
for i in range(1,aa+1):
  if aa%i==0:
  	c.append(i)

c[(len(c)//2+1):]=[]

c1=[(x) for x in c]
 
for i in c:
  for j in c1:
    if i>=j:
      continue
      
    if euc(i,j)!=1 and i!=1 and j!=1:
      if j in c:
        c.remove(j)
      
      
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import fractions

A, B = map(int, input().split())
list1 = []
add_flg = True
for i in range(1, (fractions.gcd(A, B) + 1)):
    if A % i == 0 and B % i == 0:
        for element in list1:
            if fractions.gcd(element, i) != 1:
                add_flg = False
                break
        if add_flg:
            list1.append(i)
        else:
            add_flg = True
print(len(list1))

Submission status: Time Limit Exceeded

Solution code:
def prime(n,a,b):
    num=[i for i in range(n,1,-1) if n%i ==0 and a%i == 0 and b%i == 0]
    prime=[]
    p = 2
    while p <=n**0.5 and len(num) != 0:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0]
    return prime
def chk_prime(n):
    for i in range(2,-1*int(-n**0.5//1)):
        if n%i == 0:
            return False
    return True

def main():
    a,b=map(int,input().split(' '))

    ans = 1
    if chk_prime(min(a,b)):
        if max(a,b)%min(a,b) == 0 and min(a,b) != 1:
            ans = 2
    elif chk_prime(max(a,b)):
        pass
    else:
        prime_list=prime(int(min(a,b)/2),a,b)
        for i in prime_list:
            if a%i == 0 and b%i==0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
A,B=map(int,input().split())
gcd_list=[]
so_list=[]
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def coprime(a,b):
    return gcd(a,b)==1
for num in range(1,gcd(A,B)+1):
    if A%num==0 and B%num==0:
        gcd_list.append(num)
num=len(gcd_list)
if num>4:
    gcd_list=gcd_list[:num//2]
for i in gcd_list:
    flag=0
    if len(so_list)==0:
        so_list.append(i)
    else:
        for num in so_list:
            if num==1:
                continue
            if coprime(i,num)==False:
                flag=1
                break
        if flag==0:
            so_list.append(i)
print(len(so_list))

Submission status: Time Limit Exceeded

Solution code:
import fractions
from itertools import combinations
import heapq
def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
def compromise(x1, x2):
    f = fractions.gcd(x1, x2)
    return f == 1
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
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True

a, b = map(int, input().split())
cfs = cf(a, b)
total = len(cfs)
for c in cfs:
    if not isPrime(c):
        total -= 1
print(total+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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 primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = 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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    a,b = map(int, input().split())

    li = cf(a,b)
    pli = primes(li[-1])

    c = len(set(li) & set(pli))

    print(c+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import math

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

f = [1]
for i in range(2, min(A,B)+1):
    if A % i == 0 and B % i == 0:
        f.append(i)

def isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    m = math.floor(n / 2) + 1
    for p in range(3,m,2):
        if n % p == 0:
            return False
    return True

ans = [1]
for i in f: 
    if isPrime(i):
        ans.append(i)
    
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
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)

    return divisors


#nの素数判定
def is_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 gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

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

di_A = make_divisors(A)
di_B = make_divisors(B)

di_C = list(set(di_A) & set(di_B))
if len(di_C)==1:
    print(1)
    exit()

ans = 0
array = []
array_not = []
edges = [[False] * len(di_C) for _ in range(len(di_C))]
for i in range(len(di_C)):
    for j in range(i+1, len(di_C)):
        if gcd(di_C[i], di_C[j])==1:
            edges[i][j]=True

for num in range(len(di_C), 0, -1):
    fraction = combinations(range(len(di_C)), num)
    for relation in fraction:
        judge = []
        for i, j in combinations(relation, 2):
            judge.append(edges[i][j])
        if all(judge):
            ans = num
            print(ans)
            exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def cul(a, b):
  return [i for i in range(1,min(a,b)+1) if a%i==0 and b%i==0]
a, b = list(map(int, input().split()))
cf = cul(a, b)
n = len(cf)
i = 1
while True:
  if n==1:
    print(1)
    break
  tmp = cf[i]
  for c in cf[i:]:
      if c==tmp:
        continue
      elif c%tmp==0:
        cf.remove(c)
  if cf[-1]==tmp:
    print(len(cf))
    break
  else:
    i += 1

Submission status: Time Limit Exceeded

Solution code:
import fractions
N,M=map(int,input().split())
cdiv=[]
count=1

for i in range(1,min(N,M)+1):
	if N % i == 0 and M % i == 0:
		cdiv.append(i)

x=[cdiv[0]]

for j in range(1,len(cdiv)):
	for k in range(len(x)):
		if fractions.gcd(x[k], cdiv[j])!=1 :
			break
		elif k+1==len(x):
			x.append(cdiv[j])
			count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
input = sys.stdin.readline
a, b = (int(i) for i in input().split())

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0  # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

ans = 1
x = min(a, b)

primeX = primes(x)
for prime in primeX:
    if (a % prime == 0) and (b % prime == 0):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a, b = [int(i) for i in input().split()]
small = min(a, b)
big = max(a, b)

import sys

if small == 1:
    print(1)
    sys.exit(0)

import math
table = [i for i in range(2, small + 1) if (i % 2 != 0) and (small % i == 0) and (big % i == 0)]
limit  = math.sqrt(small)
cd = []
if small % 2 == 0 and big % 2 == 0:
    cd.append(2)
while True:
    if len(table) == 0:
        break
    head = table.pop(0)
    if head > limit:
        break
    table = [v for v in table if (v % head != 0) and (small % head == 0) and (big % head == 0)]
    if (small % head == 0) and (big % head == 0):
        cd.append(head)
cd.extend(table)

print(len([i for i in cd if (small % i == 0) and (big % i == 0)]) + 1)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf8
import random

def is_prime3(q,k=1):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

A,B=map(int,input().split())
C=[1]
for i in range(2,min(A,B)+1):
    if A % i == 0 and B % i == 0:
        C.append(i)

ans=[]

for j in C:
    if is_prime3(j):
        ans.append(j)

print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

M=list(map(int,input().split()))
x=[]
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 searchPrimeNum(N):
    max = int(math.sqrt(N))
    searchList = [i for i in range(2,N+1)]
    primeNum = []
    while searchList[0] <= max:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        searchList = [i for i in searchList if i % tmp != 0]
    primeNum.extend(searchList)
    return primeNum
P=[]
x=cf(M[0],M[1])
if M[0]!=1 and M[1]!=1: 
  P=searchPrimeNum(min(M[0],M[1]))
P.append(1)
cnt=0

for i in x:
  if i in P:
    cnt+=1
    
print(cnt)