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: Wrong Answer

Solution code:

class Prime:
    def __init__(self, max_number=10000):
        '''max_numberまでの素数をprimesに入れる
        素数判定アルゴリズムはエラトステネスの篩
        fに各値を割った最小の値を格納。素数の場合0'''
        self.max_number = max_number
        self.prime_list = []
        self.f = [0 for _ in range(self.max_number+1)]
        self.f[0] = -1
        self.f[1] = -1
        for i in range(2, self.max_number+1):
            if self.f[i]:#(f[i]==0の時False)なので、f[i]に値がはいっていたら素数でないとしてcontinue
                continue
            self.prime_list.append(i)
            self.f[i] = i
            for j in range(i*i, self.max_number+1, i):
                if self.f[j] == 0:
                    self.f[j] = i
    def primes(self, x):
        '''素数のリストを返す'''
        return [n for n in self.prime_list if n <= x]

    def is_prime(self, x):
        '''xが素数ならTrue,合成数ならFalseを返す'''
        return self.f[x] == x
    def factor_list(self, x):
        '''xを素因数分解する関数
        return:素因数のリスト'''
        self.res = []
        if self.f[x] == x:
            pass
        else:
            while x != 1:
                self.res.append(self.f[x])
                x //= self.f[x]
        return self.res
    def factor(self, x):
        '''xを素因数分解する関数
        return:素因数ごとの個数'''
        self.count = {}
        if self.f[x] == 0:
            pass
        else:
            for n in self.factor_list(x):
                if n in self.count:
                    self.count[n] += 1
                else:
                    self.count[n] = 1
        return self.count
        
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

A, B = map(int, input().split())
G = gcd(A, B)
ans = 1
P = Prime(G)
ans += len(P.factor(G))
print(ans)

Submission status: Wrong Answer

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
ans = 1
while i ** 2 <= MAX:
    if A % i == 0 and B % i == 0:
        ans += 1
        while A % i == 0 and B % i == 0:
            A //= i
            B //= i
    i += 1
if A > 1 and B > 1:
    if A % B == 0 or B % A == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

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
ans = 1
while i ** 2 <= MAX:
    if A % i == 0 and B % i == 0:
        ans += 1
        while A % i == 0 and B % i == 0:
            A //= i
            B //= i
    i += 1
print(ans)

Submission status: Wrong Answer

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

i = 2
ans = 1
while i ** 2 <= MAX:
    if A % i == 0 and B % i == 0:
        ans += 1
        while A % i == 0 and B % i == 0:
            A //= i
            B //= i
    i += 1
print(ans)

Submission status: Wrong Answer

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 = list(set(p))
print(len(p))

Submission status: Wrong Answer

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 = []
for n in range(2,int(math.sqrt(x))+1):
  while x % n == 0:
    x /= n
    p.append(n)
p.append(int(x))
p = list(set(p))
print(len(p))

Submission status: Wrong Answer

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 = []
for n in range(2,int(math.sqrt(x))+1):
  if x % n == 0:
    x /= n
    p.append(n)
  else:
    p.append(int(x))
p = list(set(p))
print(len(p))

Submission status: Wrong Answer

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 = len(factorization(fractions.gcd(A,B)))
if ans == 1:
    print(ans)
else:
    print(ans+1)

Submission status: Wrong Answer

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

    arr.append([temp, 1])

    return arr
import fractions
A,B = map(int,input().split())
print(len(factorization(fractions.gcd(A,B)))+1)

Submission status: Wrong Answer

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())
print(len(factorization(fractions.gcd(A,B)))+1)

Submission status: Wrong Answer

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 = [1]
if x % 2 == 0:	p.append(2)
for val in range(3,int(x/2)+1):
  flag = 1
  if val % 2 != 0 and x % val == 0:
    for i in range(2,int(math.sqrt(val))+1):
      if val % i == 0:
        flag = 0
        break
    if flag == 1:
      p.append(val)
print(len(p))

Submission status: Wrong Answer

Solution code:
#4問目
import math
import fractions
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 isPrime(n):
    if n <= 2:
        return True
    for p in range(2, n):
        if n % p == 0:
            return False
    return True

dev = devisor(gcd)
for i in dev:
    if isPrime(i):
        count += 1
print(count)

Submission status: Wrong Answer

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())
p = [i[0] for i in factorization(a)]
q = [i[0] for i in factorization(b)]
ans = len(set(p) & set(q))
print(ans + 1)

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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 idx > 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: Wrong Answer

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

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

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

    return arr
def euclid(a, b):
  if b == 0:
    return a
  else:
    return euclid(b, a%b)
a,b=map(int,input().split())
c=euclid(a,b)
print(len(factorization(c))+1)

Submission status: Wrong Answer

Solution code:
from math import ceil
from fractions import gcd

a, b = map(int, input().split())
c = gcd(a, b)
count = 1
for num in range(2, ceil(c**0.5) + 1):
  if c % num == 0:
    count += 1
    while c % num == 0:
      c = c // num
print(count)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
a, b = map(int,input().split())
g = gcd(a,b)
p = []
d = []
for i in range(2,g):
    if g % i == 0:
        d.append(i)
for i in d:
    for j in p:
        if i % j == 0:
            break
    else:
        p.append(i)
ans = len(p) +1
print(ans)

Submission status: Wrong Answer

Solution code:
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

import math
A,B=map(int,input().split())
ans=cf(A,B)
trueans=[1]

print(ans)

while True:
    if len(ans)==0:
        break
    else:
        trueans.append(ans[0])
        tempo=[]
        for cfs in ans:
            if cfs%ans[0]==0:
                tempo.append(cfs)
        for remv in tempo:
            ans.remove(remv)

Submission status: Wrong Answer

Solution code:
import math

a,b=list(map(int,input().split()))
min_num=min(a,b)
gcd=[]

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

for i in range(1,int(math.sqrt(min_num)+1)):
  if a%i==0:
    if b%i==0:
      gcd.append(i)
    if b%(a//i)==0:
      gcd.append(a//i)

prime_list=[]
for i in gcd:
  if prime(i):
    prime_list.append(i)
print(len(prime_list))

Submission status: Wrong Answer

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


def pf(v):
    s, e = 3, v
    result = 2 if v % 2 == 0 else 1
    while v > 1 and v % 2 == 0:
        v >>= 1
    for i in range(s, e, 2):
        if v == 1:
            break
        if v % i == 0:
            result += 1
        while v > 1 and v % i == 0:
            v //= i
    return result


a, b = list(map(int, input().split()))
print(pf(gcd(a, b)))

Submission status: Wrong Answer

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


def pf(v):
    s, e = 3, v
    result = 2 if v & 1 == 0 else 1
    while v & 1 == 0:
        v >>= 1
    for i in range(s, e, 2):
        if v == 1:
            break
        if v % i == 0:
            result += 1
        while v > 1 and v % i == 0:
            v //= i
    return result


a, b = list(map(int, input().split()))
print(pf(gcd(a, b)))

Submission status: Wrong Answer

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


def pf(v):
    s, e = 3, v
    result = 2 if v & 1 == 0 else 1
    while v & 1 == 0:
        v >>= 1
    for i in range(s, e, 2):
        if v % i == 0:
            result += 1
        while v > 1 and v % i == 0:
            v //= i
    return result


a, b = list(map(int, input().split()))
print(pf(gcd(a, b)))