Problem:


Score : 400 points

Problem Statement

Given are positive integers A and B.

Let us choose some number of positive common divisors of A and B.

Here, any two of the chosen divisors must be coprime.

At most, how many divisors can we choose?

Definition of common divisor

An integer d is said to be a common divisor of integers x and y when d divides both x and y.

Definition of being coprime

Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.

Definition of dividing

An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

Constraints

All values in input are integers.

1 \leq A, B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Print the maximum number of divisors that can be chosen to satisfy the condition.

Sample Input 1

12 18

Sample Output 1

3

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.

1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Sample Input 2

420 660

Sample Output 2

4

Sample Input 3

1 2019

Sample Output 3

1

1 and 2019 have no positive common divisors other than 1.



Sample input:
12 18


Sample output:
3

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
yakusu_a = []
import math
for i in range(1, int(math.sqrt(a))+1):
  if a % i == 0:
    yakusu_a.append(i)
    if i != a//i:
      yakusu_a.append(a//i)

cd_list = []
for e in yakusu_a:
  if b % e == 0:
    cd_list.append(e)

cd_list = sorted(cd_list)

def furui(lst):
  data = lst
  ans = []
  while len(data) > 0:
    sentou = data[0]
    ans.append(sentou)
    data = [i for i in data if i % sentou != 0]
  return ans

print(len(furui(cd_list[1:]))+1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc142/tasks/abc142_d

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

# 素因数分解　何個あるかどうかを返却
def factrization(n, B):
    table = []  # 素因数を格納する
    temp = n    # nを素因数で割っていった値を一時的に格納する
    value = 0

    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

            table.append([i, cnt])

            if B % i == 0:
                value += 1


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

        if B % temp == 0:
            value += 1

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

        if B % n == 0:
            value += 1

    return value


value = factrization(A, B)

print(value + 1)

Submission status: Accepted

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

if a > b:
    a, b  = b, a
if a == 1 or b == 1:
  print(1)
  exit()

ls = []
for i in range(1, int(a**(1/2)) + 1):
    if a % i == 0:
        ls.append(i)
        ls.append(int(a/i))

ls1 = []
for j in ls:
    if b % j == 0:
        ls1.append(j)

ans = []
for k in ls1:
    if k == 1 or k == 2 or k == 3:
      ans.append(k)
      continue
    for x in range(2, int(k**(1/2)) + 1):
        if k % x == 0:
            break
        if x == int(k**(1/2)):
            ans.append(k)

print(len(ans))

Submission status: Accepted

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

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

d = gcd(a,b)
pf = {}
for i in range(2, int(d**0.5)+1):
    while d%i == 0:
        pf[i] = pf.get(i,0)+1
        d//=i
if d>1:
    pf[d] = 1
P = list(pf.keys())
print(len(P)+1)

Submission status: Accepted

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

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

def lcm(x, y):
    return x//gcd(x, y)*y

A, B = map(int, input().split())
cd = make_divisors(gcd(A, B))
ans = []
for i in range(1, len(cd)):
    flag = True
    for j in range(len(ans)):
        if cd[i]%ans[j] == 0:
            flag = False
            break
    if flag:
        ans.append(cd[i])
print(len(ans)+1)

Submission status: Accepted

Solution code:
import math
def main():
    def pri(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
    ans = 0
    a,b = map(int,input().split())
    c = pri(a)
    d = pri(b)
    p = []
    if len(c) > 0:
        p.append(c[0])
    for i in range(len(c)-1):
        if c[i] != c[i+1]:
            p.append(c[i+1])
    for i in range(len(p)):
        if p[i] in d:
            ans += 1
    print(ans+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit

from fractions import gcd

getarr = lambda _f: list(map(_f, input().split()))

a, b = getarr(int)

m = gcd(a, b)

i = 2
ans = 1
while i * i <= m:
    if m % i == 0:
        ans += 1
        while m % i == 0:
            m //= i
    i += 1

if m > 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import math

def test(a,b):
  x = gcd(a,b)
  s = []
  for i in range(2, int(math.sqrt(x)) + 1):
    while x % i == 0:
      s.append(i)
      x //= i

  s.append(x)
  s.append(1)

  return list(set(s))

def main():

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

  num = []

  num = test(a, b)
  print(len(num))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import fractions

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

maxn=10**6
prime=[1]*(maxn+1)
prime[0]=0
prime[1]=0

for i in range(2,maxn+1):
    if prime[i]==0:
        continue

    for j in range(2,maxn//i+1):
        prime[i*j]=0

C=fractions.gcd(A,B)
cnt=1

for i in range(2,maxn+1):
    if prime[i]==0:
        continue

    if C%i==0:
        while C%i==0:
            C//=i
        cnt+=1

if C>1:
    cnt+=1

print(cnt)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

A,B = inputIL()

G = gcd(A,B)

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

print(len(factorization(G))+1)

Submission status: Accepted

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

def factorization(n):
    if n < 2:
        return []

    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

def gcd(A, B):
    if B == 0:
        return A
    else:
        return gcd(B, A % B)

g=gcd(a,b)
l=factorization(g)

print(len(set(l))+1)

Submission status: Accepted

Solution code:
from fractions import gcd

N, M = map(int, input().split())

n = gcd(N, M)
# print(n)

if n == 1:
    print(1)
else:
    ans = 1

    
    for i in range(2, int(gcd(N, M)**0.5)+1):
        flag = 0
        # print("i", i)
        # print("n", n)
        if n%i == 0:
            while n%i == 0:
                n //= i
                # print(n)
            flag = 1
        # print("n", n)
        ans += flag

    print(ans if n == 1 else ans+1)

Submission status: Accepted

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

def prime_decomposition(x):
  i = 2
  table = []
  while i * i <= x:
    while x % i == 0:
      x //= i
      table.append(i)
    i += 1
  if x > 1:
    table.append(x)
  return table
  
a,b=map(int,input().split())

m=gcd(a,b)
ans=len(list(set(prime_decomposition(m))))+1
print(ans)

Submission status: Accepted

Solution code:
A,B=map(int,input().split())
import fractions 
import collections
GCD=fractions.gcd(A,B)
a=[]

while GCD % 2 ==0:
  a.append(2)
  GCD //= 2
f = 3
while f * f <= GCD:
  if GCD % f == 0:
    a.append(f)
    GCD //= f
  else:
    f += 2
if GCD != 1:
  a.append(GCD)
#print(a)
c = collections.Counter(a)
#print(c)
#print(sum(c.values())+1)
print(len(c)+1)

Submission status: Accepted

Solution code:
from fractions import gcd
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+1):
        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 == [] and n != 1:
        arr.append([n, 1])
    return arr

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

Submission status: Accepted

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

from fractions import gcd
from collections import Counter
# def gcd(x, y):
#     if x < y: x, y = y, x
#     while y != 0:
#         x, y = y, x % y
#     return x

gcd_ab = gcd(a, b)
if gcd_ab == 1:
    print(1)
    exit()

def get_divisor(n):
    divisor = Counter()
    while n % 2 == 0:
        divisor[2] += 1
        n //= 2
        
    i = 3
    while i*i <= n:
        while n % i == 0:
            divisor[i] += 1
            n //= i
        i += 2
    if n > 1:
        divisor[n] += 1
    return divisor

divisor = get_divisor(gcd_ab)
print(len(divisor)+1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


a, b = Is()

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

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

    return arr


g = gcd(a, b)
A = factorization(g)
print(len(A)+1)

Submission status: Accepted

Solution code:
import string
import collections
a_prime=[]
b_prime=[]
a,b = map(int, input().split())
def getPrime(a):
  prime=[]
  for i in range(2,int(a**0.5//1)+1):
    if a%i==0:
      while a%i == 0:
        a=a//i
      prime+=[i]
  if a!=1:
    prime.append(a)

  return prime
a_prime=getPrime(a)
b_prime=getPrime(b)
print(len(set(a_prime) & set(b_prime))+1)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from collections import Counter


def prime_factorization(n):
    """nを素因数分解する

    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す

    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m + 1 if m == 2 else m + 2  # m=3からは、m+=2する（偶数は明らかに素数ではないので）

    if n > 1:
        d[n] += 1
    return d


def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:  # コーナーケース
        print(1)
        return

    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


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

a=set(prime_decomposition(A))
b=set(prime_decomposition(B))

print(len(a&b)+1)

Submission status: Accepted

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

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

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

gcdAB = gcd(A, B)
pf = prime_factorize(gcdAB)

print(len(pf)+1)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd

input = sys.stdin.readline

def prime(n):
    primes = {}
    bound = int(math.sqrt(n)) + 1
    for i in range(2, bound):
        while n % i == 0:
            n //= i
            if not i in primes.keys():
                primes[i] = 1
            else:
                primes[i] += 1
    if n != 1:
        if n not in primes.keys():
            primes[n] = 1
        else:
            primes[n] += 1
    return primes

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

Submission status: Accepted

Solution code:
inf = 10**15
mod = 10**9+7
a,b = map(int, input().split())
import fractions

f=fractions.gcd(a,b)           #最大公約数

def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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

arr = factorization(f)
print(len(arr)+1)

Submission status: Accepted

Solution code:
'''ベスパリブ  takeg
（gcd(A, B)を素因数分解したときの素因数の個数）+1が答え。
入力例2。「420と660の正の公約数の中から、いくつか約数を選んで、
選んだやつの、どの異なる2つの整数も互いに素となる最大の約数の
個数は何か？」という問題。
420と660の正の公約数は、必ず最大公約数以下の値。
よって約数のとりうる範囲は1 ~ 最大公約数。
420と660 の最大公約数gcd(420, 660)は60。60の約数を列挙。
1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
このうち、どの2つの整数も互いに素となる約数の個数が最大となる選び方は、
1, 2, 3, 5 の4つ。
60の約数	1	2	3	4	5	6	10	12	15	20	30	60
答え	     1	 2   3		 5							
たとえば15はなぜいけないのでしょうか？それは15を素因数分解すると
15=3^1∗5^1 なので、15を選ぶと3と5が選べなくなってしまいます。 
よって15を選ぶより3と5を選んだほうが多くを選べるということ。
12や20なんかも同様の理由で選べません。
4はどうでしょうか？これは素因数分解すると4=2^2になります。
つまり4を選ぶと2を選べなくなります。この2を選ばないパターンの
1 3 4 5は、どの2つの整数も互いに素となっているのでOKです。
よって2の代わりに4を選ぶのはありですが、選ぶメリットは特にない。
素数しか選ばないというルールのほうが問題を簡単化できます。
ということで入力例2の場合では、gcd(420, 660)で最大公約数を求めて、
その最大公約数を素因数分解したときの素因数を選べば、
どの2つの整数も互いに素となります。あとついでに1も約数なので
これも加えます。これが答えになります。
制約A,B≦10^12を考えます。Nがでかすぎるので、O(N)の解法はTLE。
この問題におけるNとは、AとBの最大公約数gcd(A, B)の値です。
1～gcd(A, B)の範囲で素因数を数えることになります。
gcd(A, B)の最大値は10^12なので、O(N)は無理です。
ですが実は、最大公約数Nが何かの整数pで割り切れるときは、
N=p∗q と書けますので、p≦√N(例：N=10^12 のとき、p=10^6、q=10^6)。
なのでNまで調べる必要はなく、O(√N)で解くことができます。
コーナーケース:最大公約数が1のとき、1を出力して終了
'''
import sys
from fractions import gcd
from collections import Counter

def prime_factorization(n):
    """nを素因数分解する
    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す
    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()#インスタンス？実態は辞書。
    m = 2
    while m*m <= n:#上記に書いた上限
        while n%m == 0:#nがmで割り切れたら
            n //= m
            d[m] += 1#mで何回、割れたかを記録する
        m = m + 1 if m == 2 else m + 2  
        # m=3からは、m+=2する（偶数は明らかに素数ではないので）

    if n > 1:#sqrt(gcd(A, B)) より大きい素数が1つだけ存在しうる
        d[n] += 1
    return d

def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:  # コーナーケース
        print(1)
        return

    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
'''
（gcd(A, B)を素因数分解したときの素因数の個数）+1が答え。
入力例2を考えます。
「420と660の正の公約数の中からいくつか約数を選んで、
選んだやつのどの異なる2つの整数も互いに素となる最大の約数の個数は何か？」
という問題になります。
420と660の正の公約数は、必ず最大公約数以下の値になります。
よって約数のとりうる範囲は1 ~ 最大公約数になります。
420と660 の最大公約数gcd(420, 660)は60です。
60の約数を列挙してみます。
1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
このうち、どの2つの整数も互いに素となる約数の個数が最大となる選び方は、
1, 2, 3, 5 の4つです。見やすく表にして整理すると、
60の約数	1	2	3	4	5	6	10	12	15	20	30	60
答え	     1	 2   3		 5							
たとえば15はなぜいけないのでしょうか？それは15を素因数分解すると
15=3^1∗5^1 なので、15を選ぶと3と5が選べなくなってしまいます。 
よって15を選ぶより3と5を選んだほうが多くを選べるということになります。
12や20なんかも同様の理由で選べません。
4はどうでしょうか？これは素因数分解すると4=2^2になります。
つまり4を選ぶと2を選べなくなります。この2を選ばないパターンの
1 3 4 5は、どの2つの整数も互いに素となっているのでOKです。
よって2の代わりに4を選ぶのはありですが、選ぶメリットは特にない。
素数しか選ばないというルールのほうが問題を簡単化できます。
ということで入力例2の場合では、gcd(420, 660)で最大公約数を求めて、
その最大公約数を素因数分解したときの素因数を選べば、
どの2つの整数も互いに素となります。あとついでに1も約数なので
これも加えます。これが答えになります。
制約A,B≦10^12を考えます。Nがでかすぎるので、O(N)の解法はTLEします。
この問題におけるNとは、AとBの最大公約数gcd(A, B)の値です。
1～gcd(A, B)の範囲で素因数を数えることになります。
gcd(A, B)の最大値は10^12なので、O(N)は無理です。
ですが実は、最大公約数Nが何かの整数pで割り切れるときは、
N=p∗q と書けますので、p≦√Nとなります.
（例：N=10^12 のとき、p=10^6、q=10^6 ）。
なのでNまで調べる必要はなく、O(√N)で解くことができます。
コーナーケース:最大公約数が1のとき、1を出力して終了
'''
import sys
from fractions import gcd
from collections import Counter

def prime_factorization(n):
    """nを素因数分解する
    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す
    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m + 1 if m == 2 else m + 2  
        # m=3からは、m+=2する（偶数は明らかに素数ではないので）

    if n > 1:
        d[n] += 1
    return d

def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:  # コーナーケース
        print(1)
        return

    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import collections
import math

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

# 最大公約数を求める
smaller = min(A, B)
larger = max(A, B)

max_cd = 1
for i in range(1, int(math.sqrt(smaller))+1):
    if smaller % i == 0:
        if larger % i == 0:
            max_cd = i
        if larger % (smaller // i) == 0:
            max_cd = smaller // i
            break

#print(max_cd)

# 最大公約数を素因数分解する
c = collections.Counter()
i = 2
while i*i <= max_cd:
    if max_cd % i == 0:
        max_cd = max_cd // i
        c[i] += 1
    else:
        i += 1

if max_cd != 1:
    c[max_cd] += 1


ans = len(c.keys()) + 1
print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    a, b = MII()
    a_f = set(prime_factor(a))
    b_f = set(prime_factor(b))
    a_f.add(1)
    b_f.add(1)
    c = a_f & b_f
    print(len(c))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

def prime_factorize(N):
    res = []
    for i in range(2, int(math.sqrt(N)) + 1):
        if N % i != 0:
            continue

        num = 0
        while N % i == 0:
            N //= i
            num += 1
        
        res.append([i, num])

    if N != 1:
        res.append([N, 1])

    return res

A, B = LI()

g = gcd(A, B)
pf = prime_factorize(g)

print(len(pf) + 1)

Submission status: Accepted

Solution code:
import fractions
import math
import sys
def input(): return sys.stdin.readline().strip()


def resolve():
    a, b = map(int, input().split())
    m = fractions.gcd(a, b)

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)
            dict_counter={}
            # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter
    if m==1:
        print(1)
    else:
        d=prime_factorization_2(m)
        print(len(d)+1)


resolve()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys
from fractions import gcd
from collections import Counter
def prime_factorization(n):
    """nを素因数分解する
    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す
    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m + 1 if m == 2 else m + 2  # m=3からは、m+=2する（偶数は明らかに素数ではないので）
    if n > 1:
        d[n] += 1
    return d

def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)
    if cd == 1:  # コーナーケース
        print(1)
        return
    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(C))+1):
  while C % i == 0:
    C /= i
    prime_count[i] += 1
if C > 1:
  prime_count[int(C)] += 1

print(len(prime_count)+1)

Submission status: Accepted

Solution code:
def factorization(n):
    s = 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
            s.add(i)

    if temp != 1:
        s.add(temp)

    if len(s) == 0:
        s.add(n)

    return s


A, B = map(int, input().split())
mini = min(A, B)
maxi = max(A, B)

ss = factorization(mini)

res = 1
for i in ss:
    if maxi % i == 0:
        res += 1

if mini == 1:
    res = 1

print(res)

Submission status: Accepted

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

"""素因数分解"""
def factorization(n):
    array = [[1,1]]
    temp = n
    for i in range(2, int(math.sqrt(n))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            array.append([i, cnt])

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

    return array

factorization_array = factorization(gcd)
print(len(factorization_array))

Submission status: Accepted

Solution code:
from fractions import gcd

if __name__ == '__main__':
    def factorize(n):
        fct = []
        b, e = 2, 0
        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


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

Submission status: Accepted

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

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

A_s = set(prime_factor(A))
B_s = set(prime_factor(B))

from fractions import gcd

print(len(A_s&B_s)+1)

Submission status: Accepted

Solution code:
from fractions import gcd  #  from python3.5, use math,gcd
from collections import defaultdict


def prime_factorization(x):
    res = defaultdict(int)
    n = 2
    while n**2 <= x:
        while x % n == 0:
            res[n] += 1
            x //= n
        n += 1
    if x != 1:
        res[x] += 1
    return res


def main():
    A, B = list(map(int, input().split(' ')))
    gcd_ab = gcd(A, B)
    pf = prime_factorization(gcd_ab)
    print(1 + len(pf.keys()))  # +1 for factor `1`


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
import math 
def trial_division(n):
    #素因数を格納するリスト
    factor = [1]
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return [1, n]
    else:
        factor.append(n)
        return factor

A, B = map(int, input().split())
gcd = fractions.gcd(A, B)
N = len(set(trial_division(gcd)))
print(N)

Submission status: Accepted

Solution code:
def main():
    a, b = map(int, input().split())
    x = gcd(a, b)
    ans = prime_factorize(x)
    print(len(set(ans)) + 1)


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

#素因数分解
from collections import defaultdict
primelist=primes(int(n**0.5+1))+[n+1]
factors=defaultdict(lambda :0)
for prime in primelist:
    if prime>n:
        factors[n]+=1
        break
    while n%prime==0:
        n=n//prime
        factors[prime]+=1
factors[n]=1
factors[1]=0
print(len(factors))

Submission status: Accepted

Solution code:
import fractions

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

prime = prime_factorize(C)

print(len(set(prime))+1)