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: Accepted

Solution code:
A,B=map(int, input().split()) 
from fractions import gcd

yakusu=[]
ans=[]
bigger_val=max(A,B)
gcd_AB=gcd(A,B)

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

yakusu=sorted(make_divisors(gcd_AB))

for i in yakusu:
  if i==1:
    ans.append(i)
  else:
    if len(ans)==1:
      ans.append(i)
      #print(i,"追加")
    else:
      flag=True
      for j in ans:
        if j>1:
          if gcd(i,j)==1:
            pass
          else:
            #print(i,"は",j,"で割れる")
            flag=False
      else:
        if flag==True:
          ans.append(i)
          #print(i,"追加。",j,"までで割り切れないので。")
        
#          if i%j==0:
#            print(i,"は",j,"で割り切れるので除外")
#            break
#          ans.append(i)
#          print(i,"追加。",j,"までで割り切れないので。")           
#        else:
#          pass
      
#print(yakusu)
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
A, B=[int(i) for i in input().split()]
from copy import deepcopy as dp
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)
a_b_and = list(set(a) & set(b))
l=dp(a_b_and)
ll=[]
for i in a_b_and:
    if i==1:continue
    for j in l:
        if j%i==0 and j!=i:
            ll.append(j)
    if len(ll)>0:
        for j in ll:
            if j in l:
                l.remove(j)
print(len(l))

Submission status: Accepted

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

import math

def tn(n):
  m=n
  factor=[]
  tmp=int(math.sqrt(n))+1
  for num in range(2,tmp):
    t=0
    while n%num==0:
      n//=num
      if t==0:
        factor.append(num)
        t=1
  if factor==[]:
    factor.append(m)
  factor.append(1)
  factor.append(n)
  return factor

listA=tn(A)
listB=tn(B)
anslist=set(listA) & set(listB)
ans=len(anslist)
print(ans)

Submission status: Accepted

Solution code:
a,b = 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(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

ld=divisor(gcd(a,b))
ld.sort()
#ld.append(1)

#ld2 = divisor(gcd(a,b))
cnt=0
#print(ld)
ansl=[]
for i in ld:
    flg=0
    for j in ansl:
        #if i==j or i==1:
        #    break
        if gcd(i,j) !=1:
            flg = 1
            #print('flg',i,j)
            #if j in ld:
            #    print('in',i,j,gcd(i,j))
            #    ld.remove(j)
            break
        #print(i,j,gcd(i,j))
    if flg == 0:
        ansl.append(i)
    #print(ansl)


print(len(ansl))

#print(ld)

Submission status: Accepted

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

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

A_B_and = set(prime_factorize(A)) & set(prime_factorize(B))
print(len(A_B_and)+1)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
A, B = map(int, input().split())

glst = []
tmp = gcd(A, B)
for i in range(1, int(tmp ** 0.5) + 1):
    if tmp % i == 0:
        glst.append(i)
        if i != tmp // i:
            glst.append(tmp // i)

glst.sort()
cnt = 0
for i in range(1, len(glst) + 1):
    cntF = True
    for j in range(i + 1, len(glst) + 1):
        if gcd(glst[-i], glst[-j]) != 1:
            cntF = False
            break

    if cntF:
        cnt += 1

print(cnt)

Submission status: Accepted

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

def gcd(a, b):
  r = a % b
  if r == 0:
    return b
  return gcd(b, r)
    
r = gcd(max(a, b), min(a, b))

def yakusuu(n, r):
  res = []
  i = 0
  while True:
    i += 1
    if i*i > n:
      break
    if (n % i) != 0:
      continue
    if i <= r:
      res.append(i)
    if (n/i) == i:
      continue
    if (n/i) <= r:
      res.append(int(n/i));
  return res;

ay = yakusuu(a, r)
by = yakusuu(b, r)
l = min(len(ay), len(by))
rlist = list(set(ay) & set(by))
rlist.sort()
ans = []
for i in range(len(rlist)):
  ok = True
  for j in ans:
    if gcd(rlist[i], j) != 1:
      ok = False
      break
  if ok:
    ans.append(rlist[i])
print(len(ans))

Submission status: Accepted

Solution code:
import fractions

A, B = list(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

l = sorted(list(set(make_divisors(A)) & set(make_divisors(B))))
#print(l)
i = 0
while i < len(l):
    v = l[i]
    if v == 1:
        i += 1
        continue
    l = l[0:i+1] + list(filter(lambda x: x % v != 0, l[i+1:]))
#    print(l)
    i += 1
print(len(l))

Submission status: Accepted

Solution code:
import fractions
import collections
import math

AB = list(map(int, input().split()))
A = AB[0]
B = AB[1]

GCM = fractions.gcd(A, B)

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 isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    for p in range(2,n):
        if n % p == 0:
            return False
    return True

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

c = collections.Counter(prime_factorize(GCM))
print(len(list(c.keys()))+1)

Submission status: Accepted

Solution code:
import fractions
import copy

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

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

la=calc_divisore(a)
lb=calc_divisore(b)
ll=sorted(list(set(la)&set(lb)))
#print(la,lb,ll)
#print(ll)

ansl=[1]

ll_c=copy.copy(ll)

for i in ll_c:
#    ansl.append(i)
    len_s=len(ll)
    ll=list(filter(lambda x: fractions.gcd(i,x)==1, ll))
    if len(ll)!=len_s:
        ansl.append(i)

#   print(i,lll)
#    print(ansl)
#    print('\n')
print(len(ansl))

Submission status: Accepted

Solution code:
import fractions

A, B = map(int, input().split())
divisors = []
ans = 0
flag = 0
ans_list = []

myGCD = fractions.gcd(A, B)

for i in range(1, int(myGCD**0.5)+1):
  if myGCD % i == 0:
    divisors.append(i)
    if i != myGCD // i:
      divisors.append(myGCD//i)

divisors.sort()

for j, d in enumerate(divisors):
  for k in range(j):
    if fractions.gcd(d, divisors[k]) != 1:
      flag = 1
      break
    else:
      continue
  if flag != 1:
    ans += 1
  flag = 0

print(ans)

Submission status: Accepted

Solution code:
def euc(x,y):
  while x != y:
    if x > y:
      x -= y
    if x < y:
      y -= x
  return x

A,B = list(map(int, input().split()))
k = l = euc(A,B)
r = 1
s = 0
w = 1
while r**2 <= k:
  r += 1
  if k % r == 0:
    s += 1
    while k % r == 0:
      k /= r
    if k == 1:
      w = 0
s += w
if l != 1:
  s += 1
print(s)

Submission status: Accepted

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
A, B = map(int, input().split())


def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]


Ps = primes(1000001)
Plen = len(Ps)
As = [0] * Plen
Bs = [0] * Plen
for i, p in enumerate(Ps):
    while A % p == 0:
        A = A // p
        As[i] += 1
    while B % p == 0:
        B = B // p
        Bs[i] += 1
ans = 1
if A > 1000001 and B > 1000001 and A == B:
    ans += 1
for _ in range(Plen):
    if As[_] != 0 and Bs[_] != 0:
        ans += 1
print(str(ans))

Submission status: Accepted

Solution code:
import math
def euclid(a,b):
    if b==0:
        return a
    else:
        return euclid(b,a%b)
def 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
z=list(map(int,input().split()))
print(len(set(factorize(euclid(z[0],z[1]))))+1)

Submission status: Accepted

Solution code:
import math
from fractions import gcd
A,B = (int(i) for i in 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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = gcd(A,B)
N_divisors = make_divisors(N)
prime_nums = []
for i in range(1,len(N_divisors)):
  if i == 1:
    prime_nums.append(N_divisors[i])
  else:
    for j in range(1,i):
      if N_divisors[i]%N_divisors[j] == 0:
        break
      if j == i-1:
        prime_nums.append(N_divisors[i])

ans = 1 + len(prime_nums)
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline


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

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass

def main():
    """ main """
    A,B = map(int, input().split())
    ds = divisor(gcd(A,B))
    if len(ds) == 1:
        print(1)
        return 0
    ds = ds[1:]
    dp = [1]*len(ds)
    for i in range(len(ds)):
        if dp[i]:
            for j in range(i+1,len(ds)):
                if ds[j]%ds[i] == 0:
                    dp[j] = 0
    ans = 1
    for d in dp:
        if d == 1: ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def fatora(n):
	ans = []
	for i in range(1, n+1):
		if i*i > n:
			break
		else:
			if n % i == 0:
				ans.append(i)
				ans.append(n//i)
	return set(ans)

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


def eh_primo(n):
	if n == 0:
		return False
	elif n == 1:
		return True
	elif n == 2:
		return True
	else:
		for i in range(2, n+10):
			if i*i > n:
				break
			else:
				if n % i == 0:
					return False
		return True



a, b = map(int, input().split())
print(len(list(filter(eh_primo, fatora(gcd(a, b))))))

Submission status: Accepted

Solution code:
import math


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


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

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

yaku = sorted(divisor(A) + divisor(B))
y_list = [x for x in set(yaku) if yaku.count(x) > 1]


for r in y_list:

    if is_prime(r):
        cnt += 1

print(cnt + 1)

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
def factorization(n):
    arr = [1]
    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)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr
a = factorization(A)
b = factorization(B)
ans = len(set(a) & set(b))
print(ans)

Submission status: Accepted

Solution code:
import math

input = raw_input

def isprime(n):
    if n == 1: return True
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

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

a = []
for i in range(1,int(math.sqrt(A))+1):
    if A % i == 0:
        a.append(i)
        if i != A / i:
            a.append(A/i)

b = []
for i in range(1,int(math.sqrt(B))+1):
    if B % i == 0:
        b.append(i)
        if i != B / i:
            b.append(B/i)
c = 0
for i in a:
    if i in b and isprime(i):
        c += 1
print(c)

Submission status: Accepted

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)
  return divisors

import random

def is_prime(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
  
div=list(set(make_divisors(a))&set(make_divisors(b)))
n=len(div)
ans=0
for i in range(n):
  if is_prime(div[i]):
    ans+=1
print(ans+1)

Submission status: Accepted

Solution code:
from fractions import gcd

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())
c = gcd(a, b)
fact = factorization(c)
if fact[0][0] == 1:
    print(1)
else:
    print(len(fact) + 1)

Submission status: Accepted

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

def is_prime(num):
    if num<1:
        return False
    if num==1 or num==2 or num==3:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            return False
    return True
 
def main():
    a,b=map(int,input().split())
    GCD=gcd(a,b)
    ans=0
    for i in range(1,int(GCD**0.5)+1):
        if GCD%i==0:
            if is_prime(i):
                ans+=1
            if i!=GCD and is_prime(GCD//i):
                ans+=1
    print(ans)
    
main()

Submission status: Accepted

Solution code:
a=input().split(" ")
A=int(a[0])
B=int(a[1])
if A<B:
    A,B=B,A
while A%B!=0:
    A,B=B,A%B
if B==1:
    print(1)
else:
    count=1
    i=2
    while i**2<=B:
        if B%i==0:
            count+=1
            while B%i==0:
                B/=i
        i+=1
    if B!=1:
        count+=1
    print(count)

Submission status: Accepted

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

def factorize(n):
	b = 2
	factor = []
	while b * b <= n:
		while n % b == 0:
			n //= b
			factor.append(b)
		b = b + 1
	if n > 1:
		factor.append(n)
	
	factor = set(factor)
	return factor
    
pryA = factorize(A)
pryB = factorize(B)
 
com = (pryA & pryB)

print(len(com) + 1)

Submission status: Accepted

Solution code:
a, b = map(int, input().split(' '))
 
def divisor(n):
  ass = []
  for i in range(1,int(n**0.5)+1):
    if n%i == 0:
      ass.append(i)
      ass.append(n//i)
  return ass #sortされていない
 
a_div = divisor(a)
b_div = divisor(b)

k = []
for val in a_div:
  if val != 1 and val in b_div:
    k.append(val)
k.sort()

ans = 0
if len(k) == 0:
  ans = 1
elif len(k) == 1:
  ans = 2
else:
  ans = 2
  for i in range(1, len(k)):
    tmp = k[i]
    for j in range(0, i):
      if (tmp % k[j]) == 0:
        break
    else:
      ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
import fractions
n=fractions.gcd(a,b)

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
#print(factorization(n))
if factorization(n)==[[1,1]]:
  print(1)
else:
  print(len(factorization(n))+1)

Submission status: Accepted

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

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
res = dict(factorization(fractions.gcd(a,b)))
res[1] = 1
print(len(res))

Submission status: Accepted

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

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

div_a = make_divisors(a)
div_a.sort()
#print(div_a)
#exit()

div_b = make_divisors(b)
div_b.sort()

#print(div_a,div_b)

ans = 0
a_inc = 0
b_inc = 0
ans_list = []
"""
for i in range(len(div_a)):
    while i+a_inc < len(div_a) and i+b_inc < len(div_b):
        if div_a[i+a_inc] == div_b[i+b_inc]:
            ans += 1
            ans_list.append(div_a[i+a_inc])
            break
        elif div_a[i+a_inc] > div_b[i+b_inc]:
            b_inc += 1
        else:
            a_inc += 1
"""

while a_inc < len(div_a) and b_inc < len(div_b):
    if div_a[a_inc] == div_b[b_inc]:
        ans += 1
        ans_list.append(div_a[a_inc])
        b_inc += 1
        a_inc += 1
    elif div_a[a_inc] > div_b[b_inc]:
        b_inc += 1
    else:
        a_inc += 1


if ans == 1:
    print(ans)
    exit()
#print(div_a)
a_list = []
a_list.append(ans_list[1])

for i in range(2,ans):
    for j in range(len(a_list)):
        if ans_list[i] % a_list[j] == 0:
            break
        if j == len(a_list)-1:
            a_list.append(ans_list[i])

print(len(a_list)+1)

Submission status: Accepted

Solution code:
a, b = map(int, open(0).read().split())

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

prime_a = set(prime_factorize(a))
prime_b = set(prime_factorize(b))
print(len(prime_a&prime_b)+1)

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(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,B=two_int()

data = list(set(make_divisors(A)) & set(make_divisors(B)))

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

count=1
data.sort()
for i in data[1:]:
    if is_prime(i):
        count+=1
print(count)

Submission status: Accepted

Solution code:
import fractions
import numpy
import sys

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())
g = fractions.gcd(a, b)

if g == 1:
    print(1)
    sys.exit()

print(len(factorization(g)) + 1)

Submission status: Accepted

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

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

def coprime(a, b):
    return gcd(a, b) == 1
 
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

cmlist = sorted(list(set(divisor(A)) & set(divisor(B))))
res = []
for cm1 in cmlist:
  can_append = True
  for cm2 in res:
    if not coprime(cm1, cm2):
      can_append = False
      continue
  if can_append:
    res.append(cm1)
print(len(res))

Submission status: Accepted

Solution code:
import math
import queue
import bisect
import heapq
import time

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    g_l = divisors(g)
    ans = 1
    for i in g_l:
        if is_prime(i):
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    A,B = map(int,input().split())
    import fractions
    C = fractions.gcd(A,B)
    cnt = 0
    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
    def is_prime(n):
        if n == 1:
            return True
        for i in range(2,int(n**0.5)+1):
            if n % i == 0:
                return False
        return True
    
    C_2 = make_divisors(C)
    
    for i in C_2:
        if is_prime(i):
            cnt += 1
    print(cnt)
    
    


    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
A, B = map(int,input().split())
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

n1 = make_divisors(A)
n2 = make_divisors(B)

answer = 0
n1_n2_set = set(n1) & set(n2)
n1_n2_list = list(n1_n2_set)
common_fractions = sorted(n1_n2_list)
# print(common_fractions)
varL = []
for i in range(len(common_fractions)):
  varsum = 0
  if len(varL) >= 1:
    for j in range(len(varL)):
      # print(common_fractions[i], varL[j], fractions.gcd(common_fractions[i], varL[j]))
      if fractions.gcd(common_fractions[i], varL[j]) != 1:
        varsum += 1
    if varsum == 0:
      answer += 1
      varL.append(common_fractions[i])
  else:
    varL.append(common_fractions[i])
    answer += 1

print(answer)

Submission status: Accepted

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

def gcd(a,b):
    r = divmod(a,b)[1]
    if r == 0:
        return int(b)
    else:
        return gcd(b,r)

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


print(len(list(set(fact(gcd(A,B)))))+1)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd

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())
g = gcd(a, b) # gは最大公約数
if g == 1:
    print(1)
    sys.exit()

li = [1]
true_li = make_divisors(g)
#print(true_li)

for i in true_li:
    if i == 1:
        continue
    count = 0
    for l in li:
        if gcd(l,i) != 1:
            count += 1
    if count == 0:
        li.append(i)
print(len(li))

Submission status: Accepted

Solution code:
A, B = map(int,input().split())
import fractions
_gcd = fractions.gcd(A, B)

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

l = make_divisors(_gcd)
if len(l)==1:
    print(1)
    quit()
l.sort()
aa=False
for x in l:
    if x%2==0:
        aa=x
        break
if aa:
    l2 = [x for x in l if x%2]
    l2.append(aa)
else:
    l2 = l[:]
for i,x in enumerate(l2):
    for y in l2[i+1:]:
        if fractions.gcd(x, y) != 1 and y in l2:
            l2.remove(y)
print(len(l2))

Submission status: Accepted

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


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


if a > b:
    num = gcd(a, b)
else:
    num = gcd(b, a)


def prime(n):
    i = 2
    table = set([])
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.add(i)
        i += 1
    if n > 1:
        table.add(n)
    return len(table)


print(prime(num)+1)

Submission status: Accepted

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

import fractions
a,b=map(int,input().split())
gcd = fractions.gcd(a,b)

#print(gcd)
pnum = set()

if gcd == 1:
    print(1)
elif gcd == 2:
    print(2)
else:
    devlist = make_divisors(gcd)
    #print(devlist)
    #pnum.add(2)
    
    for num in devlist:
        if (num!=1):
            #print("gg",num)
            ptf = True
            for p in pnum:
                if num%p==0:
                    ptf = False
                    break
            if ptf ==True:
                pnum.add(num)
            
    print(len(pnum)+1)#1の分を足す

Submission status: Accepted

Solution code:
A, B = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
def cnt_pfact(n):
    ans = 1
    _n = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if _n%i==0:
            cnt=0
            while _n%i==0:
                cnt+=1
                _n //= i
            ans += 1
    if _n!=1:
        ans += 1
    return ans
  
print(cnt_pfact(gcd(A, B)))

Submission status: Accepted

Solution code:
import math

a, b = map(int, input().split())
cnt = 1
i = 2
c, d = a, b

while d > 0:
    c, d = d, c % d

k = int(math.sqrt(c))

while c > 1:
    if c % i == 0:
        cnt += 1
        
        while c % i == 0:
            c //= i

    i += 1

    if k < i:
        cnt += 1
        break

print(cnt)

Submission status: Accepted

Solution code:
a, b = [int(v) for v in input().split()]

count = 1
div = 3
if a % 2 == 0 and b % 2 == 0:
    count += 1
while a % 2 == 0:
    a //= 2
while b % 2 == 0:
    b //= 2
if a < b:
    a, b = b, a
while b >= div * div:
    if a % div == 0 and b % div == 0:
        count += 1
    while a % div == 0:
        a //= div
    while b % div == 0:
        b //= div
    div += 2
    if a < b:
        a, b = b, a
if b > 1 and a % b == 0:
    count += 1

print(count)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
import fractions
gcds=fractions.gcd(a,b)
cnt=0
primelist=[2]

while gcds%2==0:
    gcds=gcds//2
    cnt+=1
#この時点でgcdsは奇数になっているはずである
n = 10**6
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
                #エラトステネスの篩
prime.remove(2)

for some in prime:
    if gcds%some==0:
        while gcds%some==0:
            gcds=int(gcds/some)
        primelist.append(some)  

if gcds!=1 and cnt>=1:
    primelist.append("larger")
    primelist.append(1)
    
elif gcds!=1 and cnt==0:
    primelist.append("larger")
    primelist.remove(2)
    primelist.append(1)
elif gcds==1 and cnt>=1:
    primelist.append(1)
elif gcds==1 and cnt==0:
    primelist.remove(2)
    primelist.append(1)

print(len(primelist))

Submission status: Accepted

Solution code:
def prime_factor(n):
    ass = set()
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.add(i)
            n = n//i
    if n != 1:
        ass.add(n)
    return ass

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

A_set = prime_factor(A)
B_set = prime_factor(B)

num_set = A_set.intersection(B_set)

#while True:
#    if(A%i==0 and B%i==0):
#        num_set.add(i)
#        A = A//i
#        B = B//i
#        if(coprime2(A,B)==1):
#            break
#    else:
#        i = i+1
print(len(num_set)+1)