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:
def main():
    import fractions
    import math
    A, B = map(int, input().split())

    gcd = fractions.gcd(A, B)

    tmp = gcd
    ans = 1
    for i in range(2, int(-(-gcd**0.5//1))+1):
        if tmp % i == 0:
            ans += 1
            while(tmp % i == 0):
                tmp = tmp//i
    if tmp != 1:
        ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import Counter

def euclid(x, y):
    r = x % y
    if r == 0:
        return y
    else:
        return euclid(y, r)

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 = map(int, input().split())
if A > B:
    A, B = B, A
print(len(Counter(prime_factorize(euclid(A, B)))) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd
def gen(x):
    i = 2
    while i * i <= x:
        yield i
        i += 1

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    ans = 1
    for i in gen(g):
        if g % i == 0:
            ans += 1
            while(g % i == 0):g //= i
    if g != 1:ans += 1

    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
def gen(x):
    i = 1
    while i * i <= x:
        yield i
        i += 1

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    gl = []
    for i in gen(g):
        if (g % i) == 0:
            gl.append(i)
            gl.append(g // i)
    gl =set(gl)
    p = []
    for i in gl:
        b = True
        for j in gen(i):
            if j == 1:continue
            if (i % j) == 0:
                b = False
                break
        if b:
            p.append(i)
    
    print(len(p))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

gcd=fractions.gcd(A,B)
count=1

for i in range(2,int(pow(gcd,1/2))+1):
    if gcd==1:
        break
    else:
        if gcd%i==0:
            count+=1
            while gcd%i==0:
                gcd//=i
if gcd!=1:
    count+=1
print(count)

Submission status: Accepted

Solution code:
from fractions import gcd
def gen(x):
    i = 1
    while i * i <= x:
        yield i
        i += 1

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    gl = []
    for i in gen(g):
        if (g % i) == 0:
            gl.append(i)
            gl.append(g // i)
    gl =set(gl)
    p = []
    for i in gl:
        b = True
        for j in gen(i):
            if j == 1:continue
            if (i % j) == 0:
                b = False
                break
        if b:
            p.append(i)
    ans = 0
    for i in p:
        if i in p:ans+=1

    
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
import math
import numpy as np
N = list(map(int, input().split()))
g = gcd(N[0], N[1])

prime = [1]
for i in range(2, math.ceil(g**0.5)+1):
  while g % i == 0:
    g /= i
    prime.append(i)
prime.append(g)
print(len(set(prime)))

Submission status: Accepted

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

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

X = gcd(A, B)

ans_l = []
while X % 2 == 0:
    X //= 2
    ans_l.append(2)
f = 3
while f * f <= X:
    if X % f == 0:
        X //= f
        ans_l.append(f)
    else:
        f += 2
if X != 1:
    ans_l.append(X)

print(len(set(ans_l))+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
a, b = map(int, input().split())
ans = 1
for i in range(2, 1000001):
	if a%i==0 and b%i==0: ans += 1
	while a%i==0: a //= i
	while b%i==0: b //= i
if (a!=1 and b!=1) and (a%b==0 or b%a==0): ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    A, B = (int(i) for i in input().split())

    def trial_division(n):
        divs = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divs.append(i)
                if i != n//i:
                    divs.append(n//i)
        return set(divs)
    dA = trial_division(A)
    dB = trial_division(B)
    C = sorted(dA & dB)
    N = len(C)
    seen = [True]*(N)
    for i in range(1, N):
        for j in range(i+1, N):
            if seen[j] and C[j] % C[i] == 0:
                seen[j] = False
    print(seen.count(True))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def PrimeFactorization(x):
    def plist(x):
        if x < 2: return []
        if x & 1 == 0: return [2] + plist(x >> 1)
        for p in range(3, x + 1, 2):
            if x % p == 0: return [p] + plist(x // p)
            if p ** 2 > x: return [x]

    pl = plist(x)
    pp, ee = [], []
    for p in pl:
        if not pp or p != pp[-1]:
            pp += [p]
            ee += [0]
        ee[-1] += 1
    return [(p, e) for p, e in zip(pp, ee)]

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

def main():
    a,b=MI()
    g=gcd(a,b)
    pe=PrimeFactorization(g)
    print(len(pe)+1)

main()

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 prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])
    prime = []
    for p in res:
        for _ in range(p[1]):
            prime.append(p[0])
    return prime

n = gcd(a,b)
prime = set(prime_factorization(n))
print(len(prime) + 1)

Submission status: Accepted

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

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d
f = factorize(g)
print(len(f) + 1)

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)

    divisors.sort()
    return divisors

l=make_divisors(a)
ll=[]

def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y


for x in l:
    if x==1:
        continue
    if b%x==0:
        ll.append(x)
ansl=[1]
for x in ll:
    f=1
    for y in ansl:
        if gcd(x,y)!=1:
            f=0
    if f:
        ansl.append(x)


print(len(set(ansl)))

Submission status: Accepted

Solution code:
from fractions import gcd

def prime_factor(n):
    factors = set()
    i = 2
    while i * i <= n:
        while n % i == 0:
            factors.add(i)
            n //= i
        i += 1
    if n != 1:
        factors.add(n)
    return factors

A, B = map(int, input().split())
print(len(prime_factor(gcd(A, B))) + 1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().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,b = inpl()
d = make_divisors(fractions.gcd(a,b))
res = 0
for i in d:
    if is_prime(i):
        res += 1
print(res+1)

Submission status: Accepted

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

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

a, b = map(int, input().split())
pa = set(pf(a))
pb = set(pf(b))
s = pa & pb
print(len(s) + 1)

Submission status: Accepted

Solution code:
def make_prime_factors_distinct(n: int) -> list:
    """自然数nの素因数(重複なし)を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 156 -> [2, 3, 13]
    """
    prime_factors = []
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            prime_factors.append(k)
            while n % k == 0:
                n = n // k
    if n != 1:
        prime_factors.append(n)
    return prime_factors


def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


a, b = map(int, input().split()) 
res = gcd(a, b)
print(len(make_prime_factors_distinct(res)) + 1)

Submission status: Accepted

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

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

primeA = primeCount(A)
ans = 1
prd = 1
for p in sorted(primeA.keys()):
    if B % p == 0 and prd % p != 0:
        prd *= p
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

A, B = map(int, input().split())
X = gcd(A, B)
primes = []
while X % 2 == 0:
    primes.append(2)
    X //= 2
f = 3
while f * f <= X:
    if X % f == 0:
        primes.append(f)
        X //= f
    else:
        f += 2
if X != 1:
    primes.append(X)
print(len(set(primes))+1)

Submission status: Accepted

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

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

dlist = fctr1(a)
#print(dlist)
ans = 1
for i in range(len(dlist)):
    if b%dlist[i][0] == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import collections

x,y = 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
    
print(len(list(set(prime_factorize(x)) & set(prime_factorize(y)))) + 1)

Submission status: Accepted

Solution code:
import collections

x,y = 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

#素数判定(試し割り法)
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True

    limit = n ** 0.5
    for i in range(2 , n):
        if n % i == 0:
            return False
        if i >= limit: 
            return True
    print('err')

    

uoo = list(set(prime_factorize(x)) & set(prime_factorize(y)))


print(len(uoo) + 1)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        while True:
            if not n % i == 0:
                break
            ans.append(i)
            n /= i
        if n == 1:
            break
    if n != 1:
        ans.append(int(n))
    return ans

a, b = map(int, input().split())
s = set(prime_factorize(a))
t = prime_factorize(b)
ans = 1
for i in s:
    if i in t:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
ans=0
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
c=gcd(max(A,B),min(A,B))
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
div=divisor(c)
for i in range(len(div)):
    n=div[i]
    flag=1
    for i in range(2,n+1):
        if i*i>n:
            break
        if n%i==0:
            flag=0
            break
    if flag==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
    
def factorize(n):
    fct = []
    
    for i in range(2, int(n**0.5)+1):
        c = 0
        
        while n%i==0:
            n //= i
            c += 1
            
        if c>0:
            fct.append((i, c))
    
    if n>1:
        fct.append((n, 1))
    
    return fct

A, B = map(int, input().split())
G = gcd(A, B)
fct = factorize(G)
ans = 1+len(fct)

print(ans)

Submission status: Accepted

Solution code:
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, cnt])

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

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

    return arr

primef_a = factorization(a)
primef_b = factorization(b)

primef_a = [i[0] for i in primef_a]
primef_b = [i[0] for i in primef_b]

common_prime = []

for i in primef_a:
    if i != 1:
        if i in primef_b:
            common_prime.append(i)

print(len(common_prime)+1)

Submission status: Accepted

Solution code:
import collections

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

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 = map(int, input().split())
t = gcd(A, B)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    A, B = Scanner.map_int()
    A = Math.divisor(A)
    B = Math.divisor(B)
    ans = set(A) & set(B)
    print(sum(a == 1 or Math.is_prime(a) for a in ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt

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

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

def count_prime(n):
    #nを割り切る素数の個数
    if n == 1:
        return 0
    n_is_prime = True
    P = []
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            n_is_prime = False
            P.append(i)
            while n % i == 0:
                n //= i
    if n_is_prime:
        return 1
    elif n == 1:
        return len(P)
    else:
        #この時点で割り切れずに残ったnは未発見の素数
        return len(P)+1

g = gcd(A,B)
c_p = count_prime(g)
print(c_p+1)

Submission status: Accepted

Solution code:
import fractions
import math

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

def factorize(n):#素因数分解
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append([b, e])
        b, e = b + 1, 0
    if n > 1:
        fct.append([n, 1])
    return fct

d = fractions.gcd(a, b)

l = factorize(d)

print(len(l) + 1)

Submission status: Accepted

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

a, b = A, B
set_a = set([1])
set_b = set([1])

for n in range(2, int(A ** 0.5) + 1):
    if a % n == 0:
        set_a.add(n)
    while a % n == 0:
        a //= n

if a != 1:
    set_a.add(a)

for n in range(2, int(B ** 0.5) + 1):
    if b % n == 0:
        set_b.add(n)
    while b % n == 0:
        b //= n

if b != 1:
    set_b.add(b)

ans = len(set_a & set_b)
print(ans)

Submission status: Accepted

Solution code:
def bunkai(x):
    x_set = set()
    for i in range(1, int(x**0.5)+2):
        if x % i == 0:
            x_set.add(i)
            x_set.add(x//i)
    return x_set

def is_prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return None
    ans.add(x)

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

A_set = bunkai(A)
B_Set = bunkai(B)
kari = A_set & B_Set

ans = set()
for x in kari:
    is_prime(x)
print(len(ans))

Submission status: Accepted

Solution code:
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
    
def factorize(n):
    a = 2
    b = []
    while a*a <= n:
        while n%a == 0:
            b.append(a)
            n //= a
        a += 1
    if n > 1:
        b.append(n)
    return b

A, B = map(int, input().split())
print (len(set(factorize(gcd(A, B))))+1)

Submission status: Accepted

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

from fractions import gcd
from collections import defaultdict
import math
def factorize(n):
    d = defaultdict(int)

    for i in range(2, int(math.sqrt(n) + 1)):
        while n % i == 0:
            d[i] += 1
            n //= i
    if n > 1:
        d[n] += 1
    return d

ab = gcd(A, B)
d = factorize(ab)
print(len(d) + 1)

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

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

a,b = map(int, input().split())
tmp = make_divisors(a)
divisors = []
for d in tmp:
  if b%d==0:
    divisors.append(d)

arr = []
for d in divisors:
  if d==1:
    arr.append(1)
  elif is_prime(d):
    arr.append(d)
print(len(arr))

Submission status: Accepted

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

def main():
    a, b = map(int, input().split())
    c = gcd(a, b)
    pf = prime_factor(c)
    pfu = set(pf)
    print(len(pfu) + 1)

def gcd(x, y):
    if x < y:
        x, y = y, x  # x >= y
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

def prime_factor(n):
    resid = n
    result = []
    i = 2
    while True:
        if resid <= 1:
            return result
        if i ** 2 > resid:
            result.append(resid)
            return result
        if resid % i == 0:
            result.append(i)
            resid /= i
        else:
            i += 1

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

n = fractions.gcd(A, B)
if n == 1:
    print(1)
    sys.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


a = {x[0] for x in factorization(A)}
b = {x[0] for x in factorization(B)}

print(len(a & b) + 1)

Submission status: Accepted

Solution code:

from collections import defaultdict as dd
A,B = map(int,input().split())

def get_p(n):
    th = round(n**0.5)
    ans = (n,1)
    for i in range(2,th+1):
        if n % i ==  0:
            ans = (i,n//i)
            break
    return(ans)
            
def get_yakusu(n):
    flag = 1
    pn_dic = dd(lambda: 0)
    while flag:
        yaku,red = get_p(n)
        if yaku == n:
            pn_dic[str(yaku)] += 1
            flag = 0
        else:
            pn_dic[str(yaku)] += 1
            n = red
    return(pn_dic)

apn_dic = get_yakusu(A)
apn_dic["1"] += 1
bpn_dic = get_yakusu(B)
bpn_dic["1"] += 1

# print("Adic:",apn_dic)
# print("Bdic:",bpn_dic)


kouyaku_dic = dd(lambda:0)

wa_key = list(set(apn_dic.keys()) & set(bpn_dic.keys()))

for key in wa_key:
    kouyaku_dic[key] = min(apn_dic[key],bpn_dic[key])

# print("kouyaku:",kouyaku_dic)    
    
m = len(wa_key)
        
print(m)

Submission status: Accepted

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

C=1
A,B=map(int,input().split())
a=factorization(A)
b=factorization(B)
for i in range(len(a)):
 a[i][1]=0
for i in range(len(b)):
 b[i][1]=0
for i in range(len(a)):
 if a[i] in b:
  if a[i][0]>1:
   C+=1
print(C)

Submission status: Accepted

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

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

g=fractions.gcd(A, B)
#print(g)
lst=factorize(g)
#print(lst)
print(1+len(set(lst)))

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

A, B = lr()
g = gcd(A, B)

def prime_factorize(n): # 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

G = prime_factorize(g)
# 互いに素なので小さい順にgreedyに選ぶ
used = set([1])
for x in G:
    for y in used:
        if gcd(x, y) != 1:
            break
    else:
        used.add(x)

print(len(used))

Submission status: Accepted

Solution code:
import copy
a,b=map(int,input().split())
s1=set()
s2=set()
for i in range(1,int(a**0.5)+1):
  if a%i==0:
    s1.add(i)
    s1.add(a//i)
for i in range(1,int(b**0.5)+1):
  if b%i==0:
    s2.add(i)
    s2.add(b//i)
s=s1&s2
l=sorted(list(s))
for i in range(1,len(l)):
  for j in range(i+1,len(l)):
    if l[j]%l[i]==0 and l[j] in s:
      s.remove(l[j])
print(len(s))

Submission status: Accepted

Solution code:

import math


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


def prime_fact(x):
    prime_pow = {}
    check_ceil = math.ceil(math.sqrt(x))
    for p in range(2, check_ceil + 1):
        p_cnt = 0
        while x % p == 0:
            x //= p
            p_cnt += 1
        if p_cnt:
            prime_pow[p] = p_cnt
    if x > 1:
        prime_pow[x] = 1
    return prime_pow


def submit():
    a, b = map(int, input().split())
    g = gcd(a, b)
    # gcdの素因数分解して素因数の数を求める
    p = prime_fact(g)
    print(len(p) + 1)


if __name__ == "__main__":
    submit()

Submission status: Accepted

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

A = []
B = []

for i in range(1, int(a**0.5) + 1):
    if a % i == 0:
        A.append(i)
        A.append(a//i)
for j in range(1, int(b**0.5) + 1):
    if b % j == 0:
        B.append(j)
        B.append(b//j)

C = set(A) & set(B)


D = []


def uni(x):
    for i in range(1, int(x**0.5)+1):
        if x % i == 0 and i != 1:
            return False
    return True


for i in C:
    if uni(i):
        D.append(i)
print(len(D))

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)
    divisors.sort()
    return divisors
a_div=make_divisors(a)
b_div=make_divisors(b)
ab_div=a_div+b_div
ab_div.sort()
ab=[]
for i in range(len(ab_div)-1):
    if ab_div[i] == ab_div[i+1]:
        ab.append(ab_div[i])
#print(ab)
ans=[ab[0]]
for i in range(1,len(ab)):
    #print(ans)
    jagh=1
    for j in range(1,len(ans)):
        if ab[i]%ans[j] == 0:
            break
    else:
        #print("hg")
        ans.append(ab[i])
print(len(ans))

Submission status: Accepted

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    a,b = map(int, input().split())
    # 素因数分解
    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res

    c = set(prime_decomp(a))
    d = set(prime_decomp(b))
    print(len(c&d)+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def factorize(a: int) -> dict:
    """素因数分解 O(sqrt(N))
    return 素因数のdict
    """
    ps = {}
    i = 2
    nokori = a
    while i*i <= nokori:
        if nokori % i == 0:
            cnt = 0
            while nokori % i == 0:
                cnt += 1
                nokori //= i
            ps[i] = cnt
        i += 1
    if nokori != 1:
        ps[nokori] = 1
    return ps


A, B = map(int, input().split())
factor_of_a = factorize(A).keys()
factor_of_b = factorize(B).keys()
ans = len(set(factor_of_a) & set(factor_of_b))
ans += 1  # 1も
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline


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


a, b = map(int, input().split())
g = gcd(a, b)
print(len(set(prime_decomposition(g))) + 1)

Submission status: Accepted

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

def prime_factorize(n):
    s = set()
    while n % 2 == 0:
        s.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            s.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        s.add(n)
    return s
print(1+len(prime_factorize(c)))

Submission status: Accepted

Solution code:
#coding utf-8
import fractions
import math
a, b = map(int,input().split())
ans = 0
g = 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

ans = len(factorization(g)) + 1
if a == 1 or b == 1:
    ans = 1
print(ans)