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 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)
    if arr==[]:
        arr.append(n)
    return arr

A,B=map(int,input().split())
l=factorization(A)
c=0
for x in l:
    c += 1 if B%x==0 else 0
print(1 if l==[1] else c+1)

Submission status: Accepted

Solution code:
from fractions import gcd


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = 3
    while m ** 2 <= n:
        if n % m == 0:
            return False
        m += 2
    return True


A, B = map(int, input().split())
d = gcd(A, B)
n = 1
s = set()
while n ** 2 <= d:
    if d % n == 0:
        if is_prime(n):
            s.add(n)
        if is_prime(d // n):
            s.add(d // n)
    n += 1
s.add(1)
print(len(s))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import fractions
import collections
def main():
    A,B = map(int,input().split())
    gcd = fractions.gcd(A,B)
    def prime(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(gcd))
    print(len(list(c.keys()))+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def gcd(a, b):  # a,bの最大公約数
    while b:
        a, b = b, a % b
    return a

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

g = gcd(A, B)
f = prime_factor(g)

ans = len(f)
if f[0][0] != 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

#+++++
	
def gcd(a,b):
	if a < b:
		a,b = b,a
	
	while b!=1:
		tt=a%b
		if tt==0:
			return b
		a,b=b,tt
		
	return b
	
def is_sosuu(v, pl):
	if v == 2:
		return True
	if v <= 1:
		return False
	for p in pl:
		if v %p==0:
			return False
	return True
	
def bbb(val):
	return int(val**(0.5))+1
	
def main():
	b , c = map(int, input().split())
	sk=gcd(b,c)
	
	#素因数分解。素数の数+1を出力
	ans=1
	sosuu_list=[]
	using=set()
	using.add(1)
	sss=sk
	for i in range(2,bbb(sss)+1):
		while sss % i == 0:
			sss = sss // i
			using.add(i)
			if bbb(sss) < i:
				using.add(sss)
				break
	using.add(sss)
	print(len(using))
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# coding: utf-8


def factrization(n):
    arr = set()
    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.add(i)
    
    if temp != 1:
        arr.add(temp)
    
    if arr == []:
        arr.add(n)
    
    return arr

def solve():
    A, B = map(int, input().split())
    
    a_arr = factrization(A)
    b_arr = factrization(B)
    
    s_ans = a_arr & b_arr
    print(len(s_ans)+1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import random

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

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

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


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

x=[]
y=[]
z=[]

if a==1:
  x.append(1)
else:
  fct_a = factorize(a)
  for div in divisorize(fct_a):
    x.append(num(div))

if b==1:
  y.append(1)
else:
  fct_b = factorize(b)
  for div in divisorize(fct_b):
    y.append(num(div))

z=x+y
w=[m for m in set(z) if z.count(m) > 1]

c=0

for i in range(0,len(w)):
  if is_prime(w[i]):
    c+=1
print(c+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, fractions, math

def eratosthenes_sieve(n: int):
    """
    エラトステネスの篩を用いてn以下の素数を求める
    """
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def prime_factorization(n: int, prime_list: "List[int]"):
    """
    n: 素因数分解したい数
    prime_list: sqrt(n)までの素数が格納されたリスト
    -------------------
    prime_count: 素因数の個数が入ったCounterオブジェクト
    """
    import collections
    prime_count = collections.Counter()
    
    for i in prime_list:
        if i * i > n:
            break
        while n % i == 0:
            n /= i
            prime_count[int(i)] += 1
    if n > 1:
        prime_count[int(n)] += 1
    
    return prime_count

def solve(A: int, B: int):
    g = fractions.gcd(A, B)
    prime_list = eratosthenes_sieve(math.ceil(math.sqrt(g)))
    prime_count = prime_factorization(g, prime_list)
    print(len(prime_count) + 1)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

def greatest_common_divisor(N, M):
    assert N >= M
    while M != 0:
        N, M = M, N%M
    return N

def prime_divisor(N):
    temp = N
    for n in range(2, int(-(-N**0.5//1))+1):
        if temp % n == 0:
            while temp % n == 0:
                temp //= n
            yield n
    if temp != 1:
        yield temp
        

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

    if a > b:
        a, b = b, a

    gcd = greatest_common_divisor(b, a)
    pdiv = [pd for pd in prime_divisor(gcd)]
    print(len(pdiv)+1)

main()

Submission status: Accepted

Solution code:
import sys
import math


def main():
    a, b = [int(s) for s in sys.stdin.readline().strip().split()]

    def factorize(x):
        ret = set()
        for n in range(2, int(math.sqrt(x))+1):
            if x % n == 0:
                while x % n == 0:
                    x //= n
                ret.add(n)
        if x != 1:
            ret.add(x)
        return ret

    a_primes = factorize(a)
    b_primes = factorize(b)
    shared = a_primes.intersection(b_primes)
    print(len(shared) + 1)


main()

Submission status: Accepted

Solution code:
import sys
import math

def main():
    a, b = [int(s) for s in sys.stdin.readline().strip().split()]

    def factorize(x):
        ret = set()
        for n in range(2, int(math.sqrt(x))+2):
            if x % n == 0:
                while x % n == 0:
                    x //= n
                ret.add(n)
        if x != 1:
            ret.add(x)
        return ret

    a_primes = factorize(a)
    b_primes = factorize(b)
    shared = a_primes.intersection(b_primes)
    print(len(shared) + 1)


main()

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
Pa={1}
Pb={1}
a=2
while(a*a<=A):
    if A%a==0:
        A=A//a
        Pa.add(a)
    else:
        a+=1
if A>1:
    Pa.add(A)
b=2
while(b*b<=B):
    if B%b==0:
        B=B//b
        Pb.add(b)
    else:
        b+=1
if B>1:
    Pb.add(B)
print(len(Pa&Pb))

Submission status: Accepted

Solution code:
import fractions

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 = list(map(int, input().split()))

B = fractions.gcd(A[0], A[1])

C = factorization(B)

if C[0][0] != 1:
    print(len(C) + 1)
else:
    print(1)

Submission status: Accepted

Solution code:
# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# nを素因数分解したリストを返す
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 set(table+[1])

def main():
  a,b=map(int,input().split())
  print(len(prime_decomposition(gcd(a,b))))
  
main()

Submission status: Accepted

Solution code:
#abc142d

def gcd(x,y):
 while y:
  x,y=y,x%y
 return x

a,b=map(int,raw_input().split())
z=gcd(a,b)
s=set()
i=2
while i*i<=z:
 while z%i==0:
  s.add(i)
  z/=i
 i+=1
if z>1:
 s.add(z)
print len(s)+1

Submission status: Accepted

Solution code:
from math import sqrt


def solve(n):
    res = set()
    for i in range(2, int(sqrt(n))+1):
        while n % i == 0:
            res.add(i)
            n /= i
        if(n<=1): break
    if n>1:
        res.add(n)
    res.add(1)
    return res


A, B = [int(_) for _ in input().split()]
print(len(solve(A) & solve(B)))

Submission status: Accepted

Solution code:
# 2019/09/30

from fractions import gcd

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

g=gcd(a,b)


def trial_div(n):
    from collections import Counter
    
    prime=Counter()

    for i in range(2,int(pow(n,0.5)+2)):
        while n%i==0:
            n//=i
            prime[i]+=1
    if n>1:prime[n]+=1
    
    return prime


res=trial_div(g)
print(1+len(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def primes_sieve(limit):
    a = [True] * limit
    a[0] = False

    for (i, is_prime) in enumerate(a):
      p = i+1
      if is_prime:
        yield p
        for n in range(p, limit, p):
          a[n-1] = False
                
def trial_division(n):
    if n < 2:
        return set()
    prime_factors = set()
    for p in primes_sieve(int(n**0.5)):
      if p*p > n: break
      while n % p == 0:
        prime_factors.add(p)
        n //= p
    if n > 1:
        prime_factors.add(n)
    return prime_factors

A, B = map(int, input().split())
Ap = trial_division(A)
ans = [i for i in Ap if B % i == 0]
print(len(ans)+1)

Submission status: Accepted

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

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

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

print(len(set(factorize(c)))+1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def gcdx(x, y):
    g = 0
    if (x % y != 0):
        g = x % y
        gcdx(y, g)
    return g


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    #go = g
    #myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()

    price = [-1] * N
    ans = [0]*N

    for i in range(M):
        a, b = LI()
        c = LI()
        for k in c:
            if price[k-1] > a/b or price[k-1] == -1:
                price[k-1] = a/b
                ans[i] = a

    if -1 in price:
        print(-1)
    else:
        print(sum(price))

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def gcdx(x, y):
    g = 0
    if (x % y != 0):
        g = x % y
        gcdx(y, g)
    return g


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    go = g
    myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()

    price = [-1] * N
    ans = [0]*N

    for i in range(M):
        a, b = LI()
        c = LI()
        for k in c:
            if price[k-1] > a/b or price[k-1] == -1:
                price[k-1] = a/b
                ans[i] = a

    if -1 in price:
        print(-1)
    else:
        print(sum(price))

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


def gcdx(x, y):
    g = 0
    if (x % y != 0):
        g = x % y
        gcdx(y, g)
    return g


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    go = g
    myset = set([1])
    sq = int(sqrt(g)) + 2

    for i in range(2, sq):
        while g % i == 0:
            g /= i
            myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            myset.add(go)

    print(len(myset))

    return

# E


def E():
    N, M = LI()

    price = [-1] * N

    for i in range(M):
        a, b = LI()
        c = LI()
        for k in c:
            if price[k-1] > a or price[k-1] == -1:
                price[k-1] = a
    print(sum(price))

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = [1]
    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 gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)
 
A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)
 
koyaku_insu = list(set(prime_factorize(koyaku)))
 
 
print(len(koyaku_insu))

Submission status: Accepted

Solution code:
def fact(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, b = map(int, input().split())
L = set(fact(a)) & set(fact(b))
print(len(L))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2,int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]

def prime_factors(N):
    ret = []
    for p in primes(int(N ** 0.5) + 1):
        while N % p == 0:
            ret.append(p)
            N //= p
    if N > 1:
        ret.append(N)
    return ret
    
a, b = map(int, input().split())
g = gcd(a, b)
print(len(set(prime_factors(g))) + 1)

Submission status: Accepted

Solution code:
from fractions import gcd


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]


def prime_factors(N):
    ret = []
    for p in primes(int(N ** 0.5) + 1):
        while N % p == 0:
            ret.append(p)
            N //= p
    if N > 1:
        ret.append(N)
    return ret


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

Submission status: Accepted

Solution code:
from fractions import gcd


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    ret = [i for i in range(N + 1) if p[i]]
    return ret


def trial_division(N):
    factors = []
    for p in primes(int(N ** 0.5)):
        while N % p == 0:
            factors.append(p)
            N //= p
    if N > 1:
        factors.append(N)
    return factors


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

Submission status: Accepted

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

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

def factorize(a):
    ret = set()
    i = 2
    while i * i < a:
        if a % i != 0:
            i += 1
        else:
            while a % i == 0:
                a //= i
                ret.add(i)
            i += 1
    if a != 1:
        ret.add(a)
    return ret

def main():
    A, B = map(int,input().split())
    ABgcd = gcd(A, B)
    ABfactor = factorize(ABgcd)
    Ans = len(ABfactor) + 1
    print(Ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import*;g=gcd(*map(int,input().split()));s={1}
for i in range(2,int(g**.5)+1):
	while g%i<1:g//=i;s|={i}
print(len(s)+(g>1))

Submission status: Accepted

Solution code:

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


#互いに素の性質
#a, b の最大公約数 gcd(a, b) が 1 に等しい。
#aとb1、aとb2がそれぞれ互いに素ならばaとb1b2も互いに素である。
#整数 ab (a, b > 1) を選ぶよりも、a を選んだほうが良いです (注意: ab が公約数ならば a も公約数です)。
#すなわち、P を最適解とすると、P で選んだ公約数の中に ab (a, b > 1) と表せる整数が存在したとすると、代わりにa を選ぶことができます。
#よって、1 または素数のみを選んだ最適解が存在します。 
#考察も実装も簡単な方法としては、A, B をそれぞれ素因数分解し 
#(時間計算量はそれぞれ O(√A), O(√B))、共通の素因数を探す方法があります。
#1 と共通の素因数を選ぶのが最適なので、共通の素因数の個数に 1 を加えた値が答えになります。

#nの素因数分解を行いリストを返す
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_so = prime_factorize(A)
B_so = prime_factorize(B)

#与えられた素因数のリストを集合に変換(このあと共通項を見つけ出すため)
A_so = set(A_so)
B_so = set(B_so)

#集合でandを取る
A_B = A_so & B_so

#答えの出力(andの結果に 1　を加えた数が答え(1と共通の素因数を選ぶことが最適)
ans = len(A_B) + 1
print(ans)

Submission status: Accepted

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

# nの[素因数, その数]のリストを返す
def prime_factoring(n):
    from math import sqrt
    factors = []
    for num in range(2, int(sqrt(n))+1):
        if n % num == 0:
            count = 0
            while(n % num == 0):
                n //= num
                count += 1
            factors.append([num, count])
    else:
        if n != 1:
            factors.append(n)
    return factors

print(len(prime_factoring(G))+1)

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

import fractions as fs

def main():
  a, b = map(int, input().split())
  arr = factorization(fs.gcd(a, b))
  if arr[0][0] == 1:
    print(len(arr))
  else:
    print(len(arr) + 1)

if __name__ == "__main__":
  main()

Submission status: Accepted

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

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

def main():
    A, B = map(int,input().split())

    g = gcd(A, B)
    f = factorize(g)
    ans = len(f) + 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
 
D = input().split(' ')
A = int(D[0])
B = int(D[1])

result = []
result.append(1)

a_result = []
b_result = []

for i in range(2, int(A**0.5) + 2):
    flg = 0
    while A % i == 0:
        if flg == 0:
            a_result.append(i)
            flg = 1
            
        A = A / i
if A != 1:
  a_result.append(A)
        
for i in range(2, int(B**0.5) + 2):
    flg = 0
    while B % i == 0:
        if flg == 0:
            b_result.append(i)
            flg = 1
            
        B = B / i
if B != 1:
  a_result.append(B)
  
print(len(a_result) + len(b_result) - len(set(a_result + b_result)) + 1)

Submission status: Accepted

Solution code:
from collections import Counter

def prime(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())
_a_set = set(prime(_a))
_b_set = set(prime(_b))
_common_prime = _a_set & _b_set
print(len(_common_prime) + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


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


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    go = g
    myset = set([1])
    sq = int(sqrt(g)) + 2

    for i in range(2, sq):
        while g % i == 0:
            g /= i
            myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            myset.add(go)

    print(len(myset))

    return

# E


def E():
    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
def GCD(n, m):
    if n % m == 0:
        return m
    else:
        return GCD(m, n % m)

def PF(n):
    pfArray = []
    i = 2
    while (i * i <= n):
        if n % i == 0:
            pfArray.append(i)
            j = 1
            while (n % (i ** j) == 0):
                n = n / (i ** j)
        i += 1
    if n != 1:
        pfArray.append(int(n))
    return pfArray

N_i = list(map(int, input().split(" ")))
A = max(N_i)
B = min(N_i)
print(len(PF(GCD(A, B)))+1)

Submission status: Accepted

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

def factorization(n):
	lista=[]
	temp=n
	
	i=2
	while i<=int(n**0.5//1):
		if temp%i==0:
			lista.append(i)
			temp=temp//i
		else:
			i=i+1
	if temp!=1:
		lista.append(temp)
	if lista==[]:
		lista.append(n)
	
	lista.append(1)
	return lista
	
#print(factorization(a))
#print(factorization(b))

c=set(factorization(a))&set(factorization(b))
ans=len(c)
print(ans)