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:
#!/usr/bin/env python3
import fractions

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

def main():
    A, B = map(int, input().split())
    C = fractions.gcd(A,B)
    if C == 1:
        print(1)
    else:
        ans = prime_factorize(C)
        print(len(set(ans)) + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def prime_factorization(n):
    P = set()
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            P.add(i)
        i += 1
    if n > 1:
        P.add(n)

    return P

a, b = map(int, input().split())
print(len(prime_factorization(a) & prime_factorization(b)) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

g = gcd(A, B)

print(len(set(prime_decomposition(g)))+1)

Submission status: Accepted

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

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(n**0.5) + 1):
        if n % k == 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
L = make_divisors(a)
cv=[]
for i in range(len(L)):
	if b % L[i] == 0:
		cv.append(L[i])
cnt=1
cv=set(cv)
for d in cv:
	if is_prime(d):
		cnt+=1
print(cnt)

Submission status: Accepted

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

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

print(len(set(prime_factorize(fractions.gcd(a,b))))+1)

Submission status: Accepted

Solution code:

import math

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

def f(n):
  p_lis = []
  temp = n

  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      while temp % i == 0:
        temp //= i
      p_lis.append(i)
  
  if temp != 1:
    p_lis.append(temp)

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

  return p_lis

ans = set(f(A)) & set(f(B))
ans.add(1)

print(len(ans))

Submission status: Accepted

Solution code:
from itertools import chain

from math import sqrt
from collections import Counter

def prime_factorization(n):
    counter = Counter()
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            counter[i] += 1
    
    if n != 1:
        counter[n] += 1

    return counter.items()

def get_prime_facts(n):
    return set(map(lambda x: x[0], prime_factorization(n)))

def solution(A, B):
    s = get_prime_facts(A) & get_prime_facts(B) | {1}
    return len(s)

if __name__ == '__main__': 
    A, B = map(int, input().split())
    a = solution(A, B)

    print(a)

Submission status: Accepted

Solution code:
# 1, 2, 3, 5

from itertools import chain
from math import ceil

# def factorization(n):
#     tmp = n
#     arr = []
#     for i in range(2, ceil(n ** (1/2)) + 1):
#         m, r = divmod(tmp, i)
#         print(f'm: {m}, r: {r}')
#         count = 0 if r == 0 else 1
#         while r == 0:
#             m, r  = divmod(tmp, i)
#             if r == 0:
#                 tmp = m
#                 count += 1


#         if count != 0:
#             arr.append((i, count))

#     return arr

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

def get_prime_facts(n):
    return set(map(lambda x: x[0], factorization(n)))

def solution(A, B):
    s = get_prime_facts(A) & get_prime_facts(B) | {1}

    return len(s)

if __name__ == '__main__': 
    A, B = map(int, input().split())
    a = solution(A, B)

    print(a)

Submission status: Accepted

Solution code:
import collections
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 = set(prime_factorize(A))
b = set(prime_factorize(B))

ans = 1
for i in b:
  if i in a:
    ans += 1
    
print(ans)

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

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

x = gcd(a,b)

ans = len(factorization(x))+1
if factorization(x) == [[1,1]]:
  ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import fractions
A,B=map(int,input().split())
A,B=min(A,B),max(A,B)
g=fractions.gcd(A,B)
ans=1
for i in range(2,int(g**0.5+1)):
  if g%i==0:
    ans+=1
    while g%i==0:
      g/=i
    if g==1:
      break
if g!=1:
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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()
N = gcd(A, B)

print(len(factorization(N))+1 if N != 1 else 1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def is_prime(num):
	if num < 2:
		return False
	if num in [2, 3, 5]:
		return True
	if any(num%x == 0 for x in [2, 3, 5]):
		return False
	prime = 7
	step = 4
	while prime <= sqrt(num):
		if num%prime == 0:
			return False
		prime += step
		step = 6-step
	return True


A, B = MAP()

C = gcd(A, B)
ans = 1

for i in range(1, int(sqrt(C))+1):
	if C%i == 0:
		ans += is_prime(i) + is_prime(C//i)

	

print(ans)

Submission status: Accepted

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

import math

a = math.floor(math.sqrt(A))
b = math.floor(math.sqrt(B))

A_ = [1]
i = 2
while i <= a:
    if A % i == 0:
        A //= i
        A_.append(i)
    else:
        i += 1
A_.append(A)
        
B_ = [1]
i = 2
while i <= b:
    if B % i == 0:
        B //= i
        B_.append(i)
    else:
        i += 1
B_.append(B)

#print(A_)
#print(B_)
#print(set(A_))
#print(set(B_))

count = 0
for i in set(A_):
    if i in set(B_):
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

A, B = rl()

def get_divisors(n):
    divs = [1]
    for i in range(2, int(n**0.5)+1):
        c = 0
        while n % i == 0:
            n = n // i
            c += 1
        if c > 0:
            divs.append(i)
    if n > 1:
        divs.append(n)
    return divs

from fractions import gcd
divs = get_divisors(gcd(A,B))
print(len(divs))

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

A, B = rl()

def get_divisors(n):
    divs = []
    for i in range(2, int(n**0.5)+1):
        c = 0
        while n % i == 0:
            n = n // i
            c += 1
        if c > 0:
            divs.append((i, c))
    if n > 0:
        divs.append((n, 1))
    return divs

def get_ans(A, B):
	a = get_divisors(A)
	b = get_divisors(B)
	a = [k for k, c in a]+[1]
	b = [k for k, c in b]+[1]
	return len(set(a) & set(b))

ans = get_ans(A,B)
print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    g = fractions.gcd(a, b)

    def search(n):
        i = 2
        so = []
        while not(n == 1 or i * i > n):
            while n % i == 0:
                n //= i
                so.append(i)
            i += 1
        if n != 1:
            so.append(n)

        return so

    ans = set(search(g))
    print(len(ans) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def getPrimeFactors(x):
    anss = []
    while x%2 == 0:
        anss.append(2)
        x //= 2
    for d in range(3, int(x**0.5)+1, 2):
        while x%d == 0:
            anss.append(d)
            x //= d
    if x != 1:
        anss.append(x)
    return anss

PFAs = getPrimeFactors(A) + [1]
PFBs = getPrimeFactors(B) + [1]

setA = set(PFAs)
setB = set(PFBs)

ans = len(setA & setB)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B = MAP()

C = gcd(A, B)
ans = []  

def p(X):
	for i in range(2, int(sqrt(X))+1):
		if X%i == 0:
			return False
			break
	else:
		return True


for i in range(1, int(sqrt(C))+1):
	if C%i == 0:
		ans.append(p(i))
		if i != C//i:
			ans.append(p(C//i))

print(sum(ans))

Submission status: Accepted

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

if c == 1:
    print(1)
    exit()


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(len(factorization(c))+1)

Submission status: Accepted

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

def prime_factorization(n):
    dct = {}
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp == 1:
            break
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            dct[i] = cnt
    if tmp != 1:
        dct[tmp] = 1
    if len(dct) == 0:
        dct[n] = 1

    return dct

ap = prime_factorization(A)
bp = prime_factorization(B)
ap[1] = 1
bp[1] = 1

ans = 0
for p in ap:
    if p in bp:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(math.sqrt(n))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)
    return arr
  
a_list = factorization(a)
b_list = factorization(b)

a_b_and = set(a_list) & set(b_list)
print(len(a_b_and) + 1)

Submission status: Accepted

Solution code:
import math

a,b=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)

    if temp!=1:
        arr.append(temp)
    return arr
  
a_list = factorization(a)
b_list = factorization(b)

a_b_and = set(a_list) & set(b_list)
print(len(a_b_and) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd

a,b=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)

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

    return arr
  
d = gcd(a,b)
print(len(factorization(d)) + 1)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = [[1, 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, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
a, b = map(int, input().split())
g = gcd(a, b)
l = factorization(g)
print(len(l))

Submission status: Accepted

Solution code:
import math
def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    else:
        return gcd(a, b % a)

# N = int(input())
A, B = [int(_) for _ in input().split()]

gcd_ab = gcd(A, B)
cds = []
for k in range(1, math.ceil(math.sqrt(gcd_ab)) + 1):
    if gcd_ab % k == 0:
        cds.append(k)
        cds.append(gcd_ab // k)
cds = list(set(cds))
cds.sort()

ans = []
for cd in cds[1:]:
    for a in ans:
        if cd % a == 0:
            break
    else:
        ans.append(cd)

print(len(ans) + 1)

Submission status: Accepted

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

def soinsu(n):
    arr = []
    now = n
    for i in range(2, int(n**0.5)+1):
        if now%i==0:
            cnt=0
            while now%i==0:
                cnt+=1
                now //= i
            arr.append([i, cnt])

    if now!=1:
        arr.append([now, 1])

#     if arr==[]:
#         arr.append([n, 1])

    return arr

fac_a=soinsu(a)
fac_b=soinsu(b)

print( len(set(s[0] for s in fac_a) & set(s[0] for s in fac_b) )+1)

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
def pf(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
pa=set(pf(a))
pb=set(pf(b))
res = pa & pb
print(len(res)+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

# a = int(input())
a, b = list(map(int, input().split()))
# a = list(str(input()))

# com_div_list_min = [1]
# com_div_list_max = []
# if a%2==0 and b%2==0:
#     com_div_list_min.append(2)

if a != 1:
    diva_list_min = []
    diva_list_max = []
    count = 1
    while(count <= a**0.5):
        if a % count == 0:
            diva_list_min.append(count)
            diva_list_max.append(a//count)
        count += 1

    diva_list_max.reverse()
    div_a = diva_list_min+diva_list_max
else:
    div_a = [1]

com_div_ab = []
for i in (div_a):
    if b % i == 0:
        com_div_ab.append(i)


if com_div_ab == [1]:
    print(1)
    exit()

count = 1
while(count < len(com_div_ab)):
    new_com_div_ab = com_div_ab[:count+1]
    num = new_com_div_ab[-1]

    for i in range(count+1, len(com_div_ab)):
        if com_div_ab[i] % num != 0:
            new_com_div_ab.append(com_div_ab[i])
    # print(com_div_ab)
    # print(new_com_div_ab)
    # print()
    com_div_ab = new_com_div_ab
    count += 1


print(len(new_com_div_ab))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        for i in range(2, int(x**0.5)+1):
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
        if x != 1:
            res.append((x, 1))
        return res

    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import math 
def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        for i in range(2, int(math.sqrt(x))+1):
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
        if x != 1:
            res.append((x, 1))
        return res

    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import math 
def main():
    A, B = map(int, readline().split())
    def gcd(x, y):
        if not x%y:
            return y
        return gcd(y, x%y)
    
    def factorize(x):
        res = []
        for i in range(2, int(math.sqrt(x))+1):
            if x%i != 0:
                continue
            cnt = 0
            while x%i == 0:
                x //= i
                cnt += 1 
            res.append((i, cnt))
        if x != 1:
            res.append((x, 1))
        return res

    g = gcd(A, B)
    print(len(factorize(gcd(A, B)))+1) 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

c1 = collections.Counter(prime_factorize(A))
c2 = collections.Counter(prime_factorize(B))
c1_list = list(c1.keys())
c2_list = list(c2.keys())
c1_c2 = set(c1_list) & set(c2_list)
print(len(c1_c2)+1)

Submission status: Accepted

Solution code:



from collections import defaultdict


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

da = defaultdict(int)
db = defaultdict(int)



p = 2
while p * p <= A:
    while A % p == 0:
        da[p] += 1
        A //= p
    p += 1

if A != 1:
    da[A] += 1

p = 2
while p * p <= B:
    while B % p == 0:
        db[p] += 1
        B //= p
    p += 1

if B != 1:
    db[B] += 1



ans = len(set(da.keys()) & set(db.keys())) + 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def gcd(x, y):
    if x % y == 0:
        return y
    return gcd(y, x % y)


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 main():
    input = stdin.buffer.readline
    a, b = map(int, input().split())
    g = gcd(a, b)

    ans = 1
    for i in range(1, int(g ** 0.5) + 1):
        if g % i == 0:
            if is_prime(i):
                ans += 1
            if is_prime(g // i):
                ans += 1

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    z = None
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        return z


# 引用：https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
def get_fact(n):
    arr = []
    a_append = arr.append
    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
            a_append([i, cnt])

    if temp != 1:
        a_append([temp, 1])

    if not arr:
        a_append([n, 1])

    return arr


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

# check
# 参考：https://drken1215.hatenablog.com/entry/2019/10/03/175800
# ①最大公約数の素因数分解を求める
g = gcd(A, B)
fact = [f[0] for f in get_fact(g)]

# ②指数を省き、カウントする(1は確実にあるので予めカウントしておく)
elem = [1]
e_append = elem.append
for f in fact:
    if f not in elem:
        e_append(f)

print(len(elem))

Submission status: Accepted

Solution code:
import fractions, math

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

n = 2
cnt = 1
sq = math.sqrt(gcd)
while n <= sq:
    if gcd % n == 0:
        cnt += 1
        while gcd % n == 0:
            gcd = gcd // n
    n += 1
if gcd != 1:
    cnt += 1
print(cnt)

Submission status: Accepted

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

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

a_l=make_divisors(a)
b_l=make_divisors(b)
koyakusu=set(a_l)&set(b_l)
cnt=0

for k in koyakusu:
    if is_prime(k):
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
import fractions
import collections
A,B = map(int,input().split())
p = fractions.gcd(A,B)
#print(p)
num = []
for i in range(2,int(p**0.5)+1):
    while p%i==0:
        num.append(i)
        p //= i
if p != 1:
    num.append(p)
#print(num)
pp = collections.Counter(num)
print(len(pp)+1)

Submission status: Accepted

Solution code:
# D - Disjoint Set of Common Divisors

import fractions

A, B = map(int, input().split())
C = fractions.gcd(A, B)

primes = []
i = 2
while i * i <= C:
    while C % i == 0:
        C //= i
        primes.append(i)
    i += 1
if C > 1:
    primes.append(C)

print(len(set(primes)) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b=map(int,input().split())
n=gcd(a,b)
ans={1}
for i in range(2,int(n**0.5)+1):
  while n%i==0:
    n//=i
    ans.add(i)
if n>1:
  ans.add(n)
print(len(ans))

Submission status: Accepted

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

saidai_kouyaku = gcd(A,B)

#%%
kouyaku = [0 for _ in range(int(saidai_kouyaku**0.5)+2)]
kouyaku[1] = 1


for i in range(2,len(kouyaku)):
    while saidai_kouyaku%i==0:
        kouyaku[i]+=1
        saidai_kouyaku = saidai_kouyaku/i

answer = 0
for i in range(len(kouyaku)):
    if kouyaku[i] > 0:
        answer += 1

if saidai_kouyaku > 1:
    print(answer+1)
else:
    print(answer)

Submission status: Accepted

Solution code:
from fractions import gcd

def divisors(n, reverse=False):
    table = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            table.append(i)
            if i != n // i:
                table.append(n // i)
    table.sort(reverse=reverse)
    return table

def common_divisors(x, y, reverse=False):
    return divisors(gcd(x, y), reverse=reverse)


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

res = 0
for i in common_divisors(a, b):
    for k in range(2, int(i**0.5)+1):
        if i % k == 0:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')


def factorize(n):
    res = []
    for i in range(2, int(pow(n, 0.5))+1):
        if n % i: continue
        res.append([i, 0])
        while n % i == 0:
            n = n // i
            res[-1][-1] += 1
    if n != 1:
        res.append([n, 1])
    return res

from fractions import gcd
def solve():
    a, b = MI()
    p = gcd(a, b)
    f = factorize(p)
    print(len(f) + 1)






if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import collections
import math

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



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

A_div = set(make_divisors(A))
B_div = set(make_divisors(B))
common_div = (A_div & B_div)

cnt = 1
for c in common_div:
    if is_prime(c):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
"""
マスターオブ整数
公約数の問題
公約数とは最大公約数の約数であるという性質がある
"""
import fractions
A, B = map(int, input().split())

# まず公約数を列挙したくなる
# 最大公約数を求めてその約数を列挙する
# 最大公約数はユークリッドの互除法で求めることができる

ans = 1
gcd_value = fractions.gcd(A, B)
for i in range(2, int(gcd_value**0.5) + 1):
    if gcd_value % i == 0:
        ans += 1
        while gcd_value % i == 0:
            gcd_value //= i

# divisorリストの中からどの二つ互いに素となるようにいくつか選ぶ
# 素因数の数+1を答えれば良い
if gcd_value != 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import collections as col
import math

def prime(n):
    ans = []
    num = n
    for i in range(2,int(n**0.5)+1):
        if i%2==0 and i!=2: continue
        while num%i == 0: num //= i ; ans.append(i)
    if num != 1: ans.append(num)
    return ans

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

a,b = map(int,input().split())
primes = prime(gcd(a,b)) #math.gcdは使用禁止？
cnt = col.Counter(primes)
ans = len(cnt) + 1
print(ans)

Submission status: Accepted

Solution code:
import collections as col

def prime(n):
    ans = []
    num = n
    for i in range(2,int(n**0.5)+1):
        if i%2==0 and i!=2: continue
        while num%i == 0: num //= i ; ans.append(i)
    if num != 1: ans.append(num)
    return ans

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

a,b = map(int,input().split())
primes = prime(gcd(a,b))
cnt = col.Counter(primes)
ans = len(cnt) + 1
print(ans)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
a_prime_factor = []
b_prime_factor = []
for i in range(2, int(a ** 0.5) + 1):
    if a % i == 0:
        a_prime_factor.append(i)
    while a % i == 0:
        a //= i
if a != 1:
    a_prime_factor.append(a)
for i in range(2, int(b ** 0.5) + 1):
    if b % i == 0:
        b_prime_factor.append(i)
    while b % i == 0:
        b //= i
if b != 1:
    b_prime_factor.append(b)
ans = 1
for i in a_prime_factor:
    if i in b_prime_factor:
        ans += 1
print(ans)