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

def calcCommonDivisor(a, b):
    cdiv=[]
    for i in range(1, max(a,b)+1):
        if a%i==0 and b%i==0:
            cdiv.append(i)

    return cdiv

def isPrime(a):
    if a == 1:
        return True

    d=0
    for i in range(1, a+1):
        if a%i==0:
            d+=1

    return d == 2

cdiv=calcCommonDivisor(a,b)
if len(cdiv) == 1:
    print(1)
    quit()

ans=0
for i in cdiv:
    if i in (1,2,3,5,7,9):
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

from fractions import gcd as bltin_gcd

def coprime2(a, b):
    return bltin_gcd(a, b) == 1
  
A,B = map(int,input().split())

kouyaku =  cf(A,B)

for x in list(itertools.combinations(kouyaku, 2)):
    if not coprime2(x[0],x[1]):
        if x[1] in kouyaku:
            kouyaku.remove(x[1])
            
print(len(kouyaku)+1)

Submission status: Time Limit Exceeded

Solution code:
a, b = map(int, input().split())
divisor = []
elementary = [1]

for i in range(1, a+1):
    if a%i == 0 and b%i == 0:
        divisor.append(i)

num = len(divisor)

for x in divisor:
    cnt = 0
    for y in divisor:
        if x%y == 0 and x != 1:
            cnt += 1
    if cnt == 2:
        elementary.append(x)

print(len(elementary))

Submission status: Time Limit Exceeded

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

def calc_divi(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

out_A = calc_divi(A)
out_B = calc_divi(B)

tmp = list(set(out_A) & set(out_B))
tmp = sorted(tmp, reverse=True)
tmp.remove(1)

out = 0
for i in range(len(tmp)):
  jdg = 0
  for k in range(len(tmp)):
    if (tmp[i] > tmp[k] and tmp[i]%tmp[k] == 0):
        jdg = jdg + 1
        break
  if jdg == 0:
    out = out + 1

out = out + 1
print(out)

Submission status: Time Limit Exceeded

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

s = []

for i in range(2,max(A,B)-min(A,B)//2):
  if A%i==0 and B%i==0:
    s.append(i)
#print(s)
k = 0

while s:
  t = s.pop(0)
  #print(t)
  c = 0
  for j,i in enumerate(s[:]):
    if i%t==0:
      s.pop(j-c)
      c+=1
  #print(s)
  k+=1
print(k+1)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

def primelist(n):
    P = [2]
    flag = 0
    for i in range(3,n+1,2):
        for j in range(len(P)):
            if math.sqrt(i) < P[j]:
                break
            else:
                if i%P[j] == 0:
                    flag += 1
                    break
        if flag == 0:
            P.append(i)
        flag = 0
    P.append(1)
    return(P)

def maxsoin(n):
    x = n
    i = 2
    prime_factors = []
    while x > 1:
      if x % i == 0:
        prime_factors.append(i)
        x = x / i
      else:
        i += 1
    result = max(prime_factors)
    return(result)

N=gcd(A,B)

if N==1:
    print(1)
else:
    ms = maxsoin(N)
    pl = primelist(ms)
#    print(N,ms,pl)
    ans=0
    for i in range(len(pl)):
        if N%pl[i]==0:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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())
ab = cf(a, b)
del_cnt = 0
for i, ab_i in enumerate(ab):
    for j, ab_j in enumerate(ab[i+1:]):
        j = j+i+1 - del_cnt
        if ab_j%ab_i==0:
            del ab[j]
            del_cnt += 1

print(len(ab)+1)

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:
import sys
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

A, B = map(int, input().split())
gcd_AB = gcd(A, B)
if gcd_AB == 1:
  print(1)
  exit(0)
if gcd_AB == 2:
  print(2)
  exit(0)

so_list = []
for i in range(3, gcd_AB, 2):
  if A%i !=0 or B%i !=0:
    continue
  flag=True
  for s in so_list:
    if i%s == 0:
      flag=False
      break
  if flag:
    so_list.append(i)

if A%2 ==0 or B%2 ==0:
  so_list.insert(0,2)
#print(so_list)
print(len(so_list) + 1)

Submission status: Time Limit Exceeded

Solution code:
import math
a,b=map(int,input().split())
l=[]
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0:
        an=1
        for j in range(2,int(math.sqrt(i))+1):
            if i%j==0: an=0
        if an==1: l.append(i)
print(len(l)+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 = 0
    for i in li:
        for j in pli:
            if i == j:
                c += 1
                break

    print(c+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def cat(a1,a2):
    cat=[]
    for i in range(2,min(a1,a2)+1):
        if a1%i==0 and a2%i==0:
            cat.append(i)
    return cat

p, q = map(int, input().split())
pq = cat(p, q)
del_count = 0
for i, pq_i in enumerate(pq):
    for j, pq_j in enumerate(pq[i+1:]):
        j = j+i+1 - del_count
        if pq_j%pq_i==0:
            del pq[j]
            del_count += 1

print(len(pq)+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
a,b=list(map(int,input().split()))

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

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

def di(z):
  for i in range(2,int(np.sqrt(z))+1):
    if z % i == 0:
      return False
  return True

tmp=cf(a,b)
sum=0
for j in range(len(tmp)):
  if di(tmp[j]):
    sum += 1

print(sum)

Submission status: Time Limit Exceeded

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

m = max(int(a**0.5)+1, int(b**0.5)+1)
primes = [2]
count = 1

if a%2==0 and b%2==0:
    count += 1
for i in range(3,m+1):
    div = True
    for j in primes:
        if i%j==0:
            div = False
    if div:
        primes.append(i)
        if a%i==0 and b%i==0:
            count += 1

print(count)

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
    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:
#coding: utf-8
m,n = map(int,input().split())
# div = [0]
div = [1]
flg = 0
ans = 0

# if m % 2 == 0 and n % 2 == 0:
#     div.append(2)

# while i < m:
#     if m % i == 0 and n % i == 0 and i % 2 == 1:
for i in range(1,m+1):
    # print(i)
    if m % i == 0 and n % i == 0:
        ans += 1
        m = m / i
        n = n / i
        # for j in range(2,len(div)):
        #     if i % div[j] == 0:
        #         flg = 1
        #         break
        # if flg == 0:
        #     div.append(i)
        # else:
        #     flg = 0
    
# 約数を求める
# J = 2
# while j > div[len(div)]:
#     div[]
    # print(student[i]-1)
    # toukou[student[i]-1] = i+1
# print(" ".join(map(str,div)))
# print(len(div))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
a, b = (int(i) for i in input().split())
ans = 1
x = min(a, b)
if x >= 2:
    ans += 1
if x > 2:
    primes = [2]
    ix = 2
    while ix <= x//2:
        for prime in primes:
            if ix % prime == 0:
                break
        else:
            primes.append(ix)
            if (a % ix == 0) and (b % ix == 0):
                ans += 1
        ix += 1
print(ans)

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)

# print(g)
div = make_divisors(g)
# print()
p = [i for i in div[:int((len(div))/2)+1] if is_prime(i)]
# print(p)
print(len(p))

Submission status: Time Limit Exceeded

Solution code:
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

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

def coprime(a, b):
    return gcd(a, b) == 1

a,b = map(int,input().split())
cf_ab =cf(a,b)
long = len(cf_ab)


cf_ab = [i for i in cf_ab if i % 2 != 0]
if len(cf_ab) != long:
    cf_ab = [2] +cf_ab
    long = len(cf_ab)


cf_ab = [i for i in cf_ab if i % 3 != 0]
if len(cf_ab) != long:
    cf_ab = [3] +cf_ab
    long = len(cf_ab)

cf_ab = [i for i in cf_ab if i % 5 != 0]
if len(cf_ab) != long:
    cf_ab = [5] +cf_ab
    long = len(cf_ab)





cf_ab += [1]
print(len(cf_ab))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


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


A, B = map(int, input().split())
cf = cf(A, B)  
s = set()
for i in range(1, len(cf)+1):  
    for comb in list(itertools.combinations(cf, i)):
        flag = True
        for a, b in list(itertools.combinations(comb, 2)):
            if gcd(a, b) != 1:
                flag = False
        if flag:
            s.add(len(comb))
print(max(s))

Submission status: Time Limit Exceeded

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

def bunkai(n):
    sosu= {1}
    tmp = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,int(n/2)+1,2):
        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:
#coding:utf8
import random

def is_prime3(q,k=50):
    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:
A, B = [int(x) for x in input().split()]
 
s = []
 
for i in range(2,min(10**8,A,B)+1):
  if A%i==0 and B%i==0:
    s.append(i)
#print(s)
k = 0
 
while s:
  t = s.pop(0)
  #print(t)
  c = 0
  for j,i in enumerate(s[:]):
    if i%t==0:
      s.pop(j-c)
      c+=1
  #print(s)
  k+=1
print(k+1)

Submission status: Time Limit Exceeded

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

Solution code:
from sys import stdin
import sys
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 = [x for x in stdin.readline().rstrip().split()]
A = int(A)
B = int(B)
k = cf(A, B)
if len(k) == 0:
    print(1)
    sys.exit()
# print(k)
ans = []
flg = 0
idx = 0
for i in k[::-1]:
    idx = idx + 1
    for l in k[-idx::-1]:
        if i != l:
            # print(i, l)
            # print(len(cf(l,i)))
            if i > 2 and i % 2 == 0:
                flg = flg + 1
                break
            elif i > 3 and i % 3 == 0:
                flg = flg + 1
                break
            elif len(cf(l, i)) != 0:
                flg = flg + 1
                break
    if flg == 0:
        ans.append(i)
    flg = 0
# print(ans)
print(len(ans)+1)

Submission status: Time Limit Exceeded

Solution code:
tmp = input().split()
A = int(tmp[0])
B = int(tmp[1])

so = [2, 3, 5, 7, 11, 13, 17, 19]
count = 1

for i in range(2, A):
    flag = True
    if not (A % i == 0 and B % i == 0):
        continue
    for j in so:
        if i != j and i % j == 0:
            flag = False
            break
    if flag:
        count += 1

print(count)