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:
from math import gcd
from copy import copy
a, b = map(int, input().split())

def div(x):
    ret = []
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)
    
    return ret

def judge_prime(x):
    cnt = 0
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            cnt += 1
        if cnt >= 2:
            return False
    return True

div_a = div(a)
div_b = div(b)

data = list(set(div_a) & set(div_b))

ans = 0
for x in data:
    if judge_prime(x):
        ans += 1
print(ans)

Submission status: Accepted

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

def ela(g):
    s={1}
    i=2
    while i*i<=g:
        while g%i==0:
            g//=i
            s.add(i)
        i+=1
    if g!=1: s.add(g)
    return s

a,b=map(int,input().split())
G=gcd(max(a,b),min(a,b))
print(len(ela(G)))

Submission status: Accepted

Solution code:
# 2043
# 2114 解法 X,Yについて素因数分解をする．お互いに共通の素因数の数＋１が答えになるのでは？
# 約数はどっちにしても素因数もしくはその倍数になる．互いに素な共役数で素因数と合成数の両方を持つことはできないので
# 共通な素因数をたし上がればいい
# 実装
def prime_fac(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

X, Y = map(int,input().split())
X_prime = set(prime_fac(X))
Y_prime = set(prime_fac(Y))
Common = X_prime & Y_prime
print(1+len(Common))

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
def p(n):
    a = set([1])
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a
s=p(a)
l=list(s)
for x in l:
  if b%x!=0:
    s.remove(x)
print(len(s))

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
# def yaku(m):
#         ans = []
#         i = 1
#         while i*i <= m:
#             if m % i == 0:
#                 j = m // i
#                 ans.append(i)
#                 if j != i:
#                     ans.append(j)
#             i += 1
#         ans = sorted(ans)
#         return ans
a,b = readInts()
# print(yaku(a))
# print(yaku(b))
g = gcd(a,b)
# print(g)
# print(yaku(g))
def soinsu(n):
    dic = defaultdict(int)
    i = 2
    while i*i <= n:
        if n%i == 0:
            dic[i] += 1
            n //= i
        else:
            i += 1
    if n!= 1:
        dic[n] += 1
    return dic
dic = soinsu(g)
cnt = 1 # 1
for k,v in dic.items():
    cnt += 1
print(cnt)
# a //= g
# b //= g
# print(a,b)

Submission status: Accepted

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

#素因数分解して列挙する関数、約数列挙ではない！
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)
    fct = list(set(fct))
    return fct

f = factorize(g)
ans = len(f)+1
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def divisor(n):
  ass=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ass.append(i)
      if i!=n//i:ass.append(n//i)
  return ass
def is_prime(n):
  if n==1:return True;return False
  for i in range(2,int(n**0.5)+1):
    if n%i==0:return False
  return True
ans=0
a,b=map(int,input().split())
for i in divisor(gcd(a,b)):
  if is_prime(i):ans+=1
print(ans)

Submission status: Accepted

Solution code:
A, B = map(int,input().split())
P = [1]
a = set([1,A])
b = set([1,B])
for k in range(2,2+int(max(A,B)**(1/2))):
    if A%k == 0 and B%k == 0:
        P.append(k)
        a.add(A//k)
        b.add(B//k)
    elif A%k == 0:
        a.add(A//k)
    elif B%k == 0:
        b.add(B//k)

P += list(a&b)
P.sort()
U = set([])
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
for e in P:
    flag = 1
    for used in U:
        if gcd(e,used) != 1:
            flag = 0
            break
    if flag == 1:
        U.add(e)
print(len(U))

Submission status: Accepted

Solution code:
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
P = [1 for _ in range(10**6)]
P[0]=0
P[1]=0
for i in range(2,10**3):
    for j in range(i*i,10**6,i):
        P[j] = 0
Q = []
for i in range(2,10**6):
    if P[i]==1:
        Q.append(i)
A,B = map(int,input().split())
N = gcd(A,B)
R = [1]
for p in Q:
    if N%p==0:
        R.append(p)
        while N%p==0:
            N = N//p
if N>1:
    R.append(N)
print(len(R))

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

def lcm(a, b):
    return a // gcd(a, b) * b
x=gcd(a,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
y=prime_factorize(x)
print(len(set(y))+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

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

ab = list(set(make_divisors(a)) & set(make_divisors(b)))

ans = 1
for i in ab[1:]:
    if is_prime(i): ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
# debug = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

A, B = inm()


def solve():
    x = fractions.gcd(A, B)
    ans = 0
    for k in range(2, x + 1):
        if k * k > x:
            break
        cnt = 0
        while x % k == 0:
            x //= k
            cnt += 1
        if cnt:
            ans += 1
    if x > 1:
        ans += 1
    return ans + 1


print(solve())

Submission status: Accepted

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

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

import math
def factorize(n):
    d = {}
    temp = int(math.sqrt(n))+1
    for i in range(2, temp):
        while n%i== 0:
            n //= i
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    if d == {}:
        d[n] = 1
    else:
        if n in d:
            d[n] += 1
        elif n != 1:
            d[n] =1
    return d

d = factorize(g)
print(len(d)+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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())
fct = factorize(gcd(A, B))
ans = 1+len(fct)
print(ans)

Submission status: Accepted

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


def prime_numbers(n):
    """n以下の素数列挙"""
    eratosthenes = [True] * (n + 1)
    eratosthenes[1] = False
    prime_list = []
    for i in range(2, n + 1):

        if eratosthenes[i]:
            k = 2
            while True:
                if i * k < n + 1:
                    eratosthenes[i * k] = False
                    k += 1
                else:
                    break
            prime_list.append(i)
    return prime_list


def prime_factorization(n: int):
    factors = []
    tmp_n = n
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        count_divide = 0
        while True:
            tmp_n = n
            s, r = divmod(tmp_n, i)
            if r == 0:
                count_divide += 1
                n = s
            else:
                break
        if count_divide >= 1:
            factors.append([i, count_divide])
    if tmp_n > 1:
        factors.append([tmp_n, 1])
    return factors


a_b_max = max(A, B)
a_b_min = min(A, B)
max_factors = prime_factorization(a_b_max)
min_factors = prime_factorization(a_b_min)
j = 0
ans = 1
for p, i in max_factors:
    while True:
        if j == len(min_factors):
            break
        if min_factors[j][0] == p:
            ans += 1
            j += 1
        elif min_factors[j][0] < p:
            j += 1
        else:
            break

print(ans)
# ans = 1
# for p in prime_list:
#     a_s, a_r = divmod(A, p)
#     b_s, b_r = divmod(B, p)
#     if A % p == 0 and B % p == 0:
#         ans += 1

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
while a!=0:
  c=a
  a=b%a
  b=c
ans=1
for i in range(2,int(math.sqrt(b)+2)):
  if b%i==0:
    ans+=1
    while b%i==0:
      b=int(b/i)
if b!=1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル

    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()

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

    a = make_divisors(a)
    b = make_divisors(b)

    # 公約数 = 一致する値。
    a_b_divisor = list(set(a) & set(b))

    a_b_divisor.sort()

    if len(a_b_divisor) <= 1:
        print(len(a_b_divisor))
        return

    # エラストテネスの篩
    aa = -1
    for i in a_b_divisor[1:]:
        if len(a_b_divisor) <= 1:
            break

        if i > a_b_divisor[-1] / 2:
            break

        aa += 1
        sieve = i

        new_list = []

        for j in a_b_divisor:
            if j <= i or not j % sieve == 0:
                new_list.append(j)

        a_b_divisor = new_list

    print(len(a_b_divisor))

# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """12 18"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """420 660"""
        output = """4"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """1 2019"""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
def main():
    a, b = list(map(int, input().split()))
    def factorization(num):
        result = set()
        count = 0
        temp = num
        for i in range(2, int(num ** 0.5) + 1):
            if temp % i == 0:
                count = 0
                while temp % i == 0:
                    count += 1
                    temp /= i
                result.add(i)
        if temp != 1:
            result.add(int(temp))
        if result == []:
            result.add(num)
        return result
    print(len(factorization(a) & factorization(b)) + 1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
def factor(n):
    res = []
    for i in range(2,int(n**0.5)+1):
        while n % i == 0:
            res.append(i)
            n //= i
    if n > 1:
        res.append(n)
    return res

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

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

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

    return arr

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

g = gcd(a,b)
f = factorization(g)
ans = 1

for i,j in f:
  if i == 1:
    continue
  ans += 1

print(ans)

Submission status: Accepted

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

import math

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

    return True


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1

    return lower_divisors + upper_divisors[::-1]


def gcd(a, b):

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


da = make_divisors(A)
common_divisors = []

for d in da:
    if B % d == 0:
        common_divisors.append(d)

ans = [1 if is_prime(x) else 0 for x in common_divisors]
print(sum(ans))

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

Submission status: Accepted

Solution code:
import fractions
import math

def primefac(n):
    ret = []
    e = 0
    for i in range(2, math.floor(n**(1/2)) + 1):
        if n % i == 0:
            e = 0
            while n % i == 0:
                e += 1
                n //= i
            ret.append((i, e))
    if n != 1:
        ret.append((n, 1))
    return ret

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MAX = max(A, B)

i = 2
setA = set()
setB = set()
while i ** 2 <= A:
    if A % i == 0:
        while A % i == 0:
            A //= i
        setA.add(i)
    i += 1
if A > 1:
    setA.add(A)
i = 2
while i ** 2 <= B:
    if B % i == 0:
        while B % i == 0:
            B //= i
        setB.add(i)
    i += 1
if B > 1:
    setB.add(B)

print(len(setA & setB) + 1)

Submission status: Accepted

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

# 最大公約数の算出
y = max(A,B)
x = min(A,B)
while y%x != 0:
  tmp = x
  x = y%x
  y = tmp

# 素因数分解
p = []
tmp = int(math.sqrt(x))+1
for n in range(2,tmp):
  while x % n == 0:
    x /= n
    p.append(n)
p.append(int(x))
p.append(1)
p = list(set(p))
print(len(p))

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
A,B = map(int,input().split())
ans = factorization(fractions.gcd(A,B))
if ans[0][0] == 1:
    print(len(ans))
else:
    print(len(ans)+1)

Submission status: Accepted

Solution code:
#4問目
import math
import fractions
import collections
A, B = map(int, input().split())

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

def devisor(num):
    array = []
    for i in range(1, math.floor(math.sqrt(num)) + 1):
        if(num % i == 0):
            array.append(i)
            array.append(math.floor(num / i))
    return array

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

print(len(collections.Counter(prime(gcd))) + 1)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
a, b = map(int, input().split())
if a == b == 1:
    print(1)
    sys.exit()
p = [i[0] for i in factorization(a)]
q = [i[0] for i in factorization(b)]
# print("p =", p)
# print("q =", q)
ans = len(set(p) & set(q))
# print(ans)
print(ans + 1)

Submission status: Accepted

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

arr = []#素数リスト　(素数:べき)の形で出てくる

def factorization(n):
    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])

factorization(a)
ans = 0

for p,n in arr:
  if b%p == 0:
    ans += 1
    
if len(arr) == 1 and arr[0][0] == 1:
  print(1)
  exit()
  
print(ans+1)

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

class Mint(object):
    """ 整数のお役立ち計算
    - 繰り返し二乗法で効率的にn**kを求める（必要であればmodを指定）
    - 素数判定
    - 素因数分解
    - 約数列挙
    - nCrの計算(ピンポイントで求める or あるnまでのnCrを計算するのに必要な情報を一気に求める）
    - ToDo:
    # divisor : 配列をsortしているため遅い可能性あり
    """

    def gcd(self, a, b):
        # ユークリッドの互除法を用いる
        while b:
            a, b = b, a % b
        return a

    def lcm(self, a, b):
        return a * b // self.gcd(a, b)

    @staticmethod
    def cmb_(n, r):
        """ 普通にnCrを求める
        >>> p = Mint()
        >>> p.cmb_(10, 2)
        45
        """
        from operator import mul
        from functools import reduce

        r = min(n - r, r)
        if r == 0:
            return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1, r + 1))
        return over // under

    def cmb(self, n, r, mod: int = 10 ** 9 + 7):
        """ 事前にあるnまでの範囲で、nCrを高速に計算する
        >>> p = Mint()
        >>> p.cmb_prep(10)
        >>> p.cmb(10, 2)
        45
        """
        if (r < 0) or (r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % mod

    def cmb_prep(self, N: int, mod: int = 10 ** 9 + 7):
        self.g1 = [1, 1]  # 元テーブル
        self.g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

        for i in range(2, N + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    @staticmethod
    def iterated_power(z: int, n: int, mod=None) -> int:
        """ 繰り返し二乗法でn**kを求める（再帰処理は使わない）
        >>> p = Mint()
        >>> p.iterated_power(3, 10)
        59049
        >>> p.iterated_power(3, 10, 10)
        9
        """
        beta = bin(n)[2:]

        Z, q, t = z, 0, len(beta)
        while beta[t - q - 1] == '0':
            Z = Z * Z
            if mod is not None:
                Z = Z % mod
            q += 1
        result = Z

        for k in range(q + 1, t):
            Z = Z * Z
            if mod is not None:
                Z = Z % mod
            if beta[t - k - 1] == '1':
                result = result * Z
                if mod is not None:
                    result = result % mod

        if mod is not None:
            result = result % mod

        return result

    @staticmethod
    def factorization(n: int) -> dict:
        from collections import defaultdict

        arr = defaultdict(int)
        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[i] = cnt

        if temp != 1:
            arr[temp] = 1

        if arr == []:
            arr[n] = 1

        return arr

    @staticmethod
    def enumerate_prime(n: int) -> (list, dict, list):
        """
        n以下の素数を列挙する
        何で割るかを記録しておくことで、素因数分解が高速にできる
        >>> p = Mint()
        >>> p.enumerate_prime(11)
        ([2, 3, 5, 7, 11], {2: 0, 3: 1, 5: 2, 7: 3, 11: 4}, [0, 1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11])
        """

        lis_prime = [True] * (n+1)
        lis_prime[0] = False
        lis_prime[1] = False

        primes = []
        div_prime = [i for i in range(n + 1)]
        primes_idx = {}

        cnt = 0
        for i in range(2, n+1):
            if lis_prime[i]:
                primes.append(i)
                primes_idx[i] = cnt
                cnt += 1

                j = 2 * i
                while True:
                    if j > n:
                        break
                    lis_prime[j] = False
                    div_prime[j] = i
                    j += i

        return primes, primes_idx, div_prime

    @staticmethod
    def is_prime(n: int) -> bool:
        """
        素数判定
        >>> p = Mint()
        >>> p.is_prime(2)
        True
        >>> p.is_prime(43)
        True
        >>> p.is_prime(4)
        False
        """

        if n == 1:
            return False
        if n == 2:
            return True

        for i in range(2, n):
            if n % i == 0:
                return False
            if i * i > n:
                return True

    @staticmethod
    def divisor(n: int) -> list:
        """
        約数列挙
        >>> p = Mint()
        >>> p.divisor(6)
        [1, 2, 3, 6]
        """
        res = []
        if n == 1:
            return [1]

        for i in range(1, n):
            if n % i == 0:
                res.append(i)
                if i != n / i:
                    res.append(int(n / i))
            if (i+1) * (i+1) > n:
                res.sort()
                return res

mint = Mint()
c = mint.gcd(a, b)
# print(c)
candidates = mint.divisor(c)[1:]
# print(candidates)
res = [True] * len(candidates)

for idx, i in enumerate(candidates):
    # if i > len(candidates)**.5:
    #     break
    for j in range(idx+1, len(candidates)):
        if candidates[j] % i == 0:
            res[j] = False

ans = 1
for i in res:
    if i:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
sqrt = math.floor(g ** 0.5)
factors = [1]
z = g
for i in range(2, sqrt + 1):
    if not z % i:
        factors.append(i)
        while z % i == 0:
            z //= i
if z > 1:
    factors.append(z)
print(len(factors))

Submission status: Accepted

Solution code:
def factorization(n):
    factorization_list = [1]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp //= i
            factorization_list.append(i)

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

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

    return factorization_list


if __name__ == "__main__":
    A, B = map(int, input().split())
    A_fac = set(factorization(A))
    B_fac = set(factorization(B))

    AB_fac = A_fac & B_fac
    print(len(AB_fac))

Submission status: Accepted

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

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

g=gcd(a,b)

f=set()
for i in range(1,int(g**0.5)+1):
  if g%i==0:
    for j in range(2,int(i**0.5)+1):
      if i%j==0:
        break
    else:
      f.add(i)
    p=g//i
    for j in range(2,int(p**0.5)+1):
      if p%j==0:
        break
    else:
      f.add(p)

print(len(f))