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:
from fractions import gcd

def primeNum(n):
    prime=[1,2]
    for k in range(3, n+1):
        if n % k == 0:
          if isPrime(k):
            prime.append(k)
    return prime

def isPrime(m):
  if m%2==0: return False
  for j in range(2, int(m**0.5)+1):
    if m%j == 0: return False
  return True

a,b = list(map(int, input().split()))
n=gcd(a,b)
print(len(primeNum(n)))

Submission status: Wrong Answer

Solution code:

A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= [1]
    tmp = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.append(2)
    
    stop_flag = n//2

    for i in range(3,int(n/2)+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.append(i)
        if i > stop_flag:
            break
        else:
            stop_flag //=i 
            
    if tmp!=1:
        sosu.append(tmp)
                
    if sosu==[]:
        sosu.append[n]
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import math

A,B = map(int,input().split())
g = fractions.gcd(A,B)
# g = math.gcd(A,B)
lim = math.ceil(math.sqrt(g))
c = 0
for i in range(2,lim+1) :
    if (g % i == 0) :
        c += 1
        while(True) :
            # 割り切れるまで割れば合成数は除外できる
            g = g / i
            if (g % i != 0) :
                break
        
print(c+1)

Submission status: Wrong Answer

Solution code:
a, b = [int(i) for i in input().split()]
small = min(a, b)
big = max(a, b)

import sys

if small == 1:
    print(1)
    sys.exit(0)

import math

#prime_flag = [True] * (small + 1)
#limit  = int(math.sqrt(small))
#for i in range(2, limit + 2):
#    if not prime_flag[i]:
#        continue
#    for j in range(i + i, small + 1, i):
#        prime_flag[j] = False

#primes = [i for i, _ in enumerate(prime_flag) if prime_flag[i]][2:]
#cd = [p for p in primes if (small % p == 0) and (big % p == 0)]
#
#print(len(cd) + 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def main():
    A,B = map(int,input().split())
    An = prime_factorize(A)
    Bn = prime_factorize(B)
    An.extend(Bn)
    Cn = [x for x in set(An) if An.count(x) > 1]
    print(len(Cn)+1)

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

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    f = int(min(max(a, b) ** 0.5, min(a, b)))
    ls = [True] * (f + 1)
    ls[0] = False
    ls[1] = False
    cnt = 1
    for i in range(len(ls)):
        if ls[i]:
            if a % i == 0 and b % i == 0:
                cnt += 1
            for j in range(i, len(ls), i):
                if ls[j]:
                    ls[j] = False
    if a == b:
        cnt += 1
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

Solution code:
import fractions
import math

def trial_division(n):
    a = [1]
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a


A, B = map(int, input().split())
max_n = fractions.gcd(A,B)

ans = set(trial_division(max_n))
print(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import fractions
def main():
    A,B = map(int,input().split())
    gcd = fractions.gcd(A, B)
    Cn = prime_factorize(gcd)
    print(len(Cn)+1)

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

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    f = int(min(max(a, b) ** 0.5, min(a, b)))
    ls = [True] * (f + 1)
    ls[0] = False
    ls[1] = False
    cnt = 1
    p = True
    for i in range(len(ls)):
        if ls[i]:
            if a % i == 0 and b % i == 0:
                cnt += 1
                if p:
                    p = False
            for j in range(i, len(ls), i):
                if ls[j]:
                    ls[j] = False
    if a == b and p:
        cnt += 1
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

Solution code:
import fractions
import math

def trial_division(n):
    a = []
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a


A, B = map(int, input().split())
max_n = fractions.gcd(A,B)

ans = set(trial_division(max_n))

print(len(ans))

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math
m,n = map(int,input().split())
ans = 1

# GCD(Grate Common Divisier) を求める
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

gcd_cnt = gcd(m,n)
print(gcd_cnt)

# GCDの約数を素因数分解する
flg = 0
i = 2
aaa = gcd_cnt
while i <= gcd_cnt:
    print(str(i)+str(',')+str(gcd_cnt))
    if gcd_cnt % i == 0:
        flg = 1
        gcd_cnt = gcd_cnt // i
    else:
        if flg == 1:
            ans +=1
            flg = 0
        i+=1
    if i > aaa/2:
        i = aaa
if flg == 1:
    ans += 1

# if m % 2 == 0 and n % 2 == 0:
#     div.append(2)

# for i in range(1,m+1):
#     # print(i)
#     if m % i == 0 and n % i == 0:
#         ans += 1
#         # m = m / i
#         # n = n / i
#         div.append(i)
#         # for j in range(2,len(div)):
#         #     if i % div[j] == 0:
#         #         flg = 1
#         #         break
#         # if flg == 0:
#         #     div.append(i)
#         # else:
#         #     flg = 0
    
# print(" ".join(map(str,div)))
# div.sorted(reversed=True)

# for j in range(1,div[0]):
#     div[0] % j


# # print(len(div))
print(ans)