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:
A, B = sorted([int(i) for i in input().split()])

res = 1
for i in range(2, int(B**0.5)+1):
    if B % i == 0:
        if A % i == 0:
            for j in range(2, int(i**0.5)+1):
                if i % j == 0:
                    break
            else:
                res += 1
        t = B // i
        if t != i and A % t == 0:
            for j in range(2, int(t**0.5)+1):
                if t % j == 0:
                    break
            else:
                res += 1

print(res if res > 1 else (1 if A != B else 2))

Submission status: Wrong Answer

Solution code:
#import sys

#input = sys.stdin.readline

#import heapq
import math
import fractions

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

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=2
    k=1

    count=1
    if a>b:
        a,b=b,a
    sosu=set()
    #d = math.gcd(a,b)
#    print(d)
    c=math.sqrt(a)+111
    while m<c and m<=a:
        if a%m==0:
            sosu.add(m)
            while a%m==0:
                a//=m

        m+=1

 #   print(sosu)
    for i in sosu:
        if b%i==0:
            count+=1



    print(count)
#    for i in range(h):
#            print(aaa)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
A, B = sorted([int(i) for i in input().split()])

res = 1 if A != B else 2
for i in range(2, int(B**0.5)+1):
    if B % i == 0:
        if A % i == 0:
            for j in range(2, int(i**0.5)+1):
                if i % j == 0:
                    break
            else:
                res += 1
        t = B // i
        if t != i and A % t == 0:
            for j in range(2, int(t**0.5)+1):
                if t % j == 0:
                    break
            else:
                res += 1

print(res)

Submission status: Wrong Answer

Solution code:
# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数を２つのグループに分ける

import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = [1]
  fac = facto(c, fac)
  # print(fac)
  print(len(fac))  
  
def facto(n, fac):
  if n == 1:
    return [1]
  if n == 2:
    return[1, 2]
  if n % 2 == 0:
    fac = [1, 2]
  else:
    fac = [1]
  
  max_n = int(n ** 0.5 + 2)
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 1):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n //= cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
      
  return fac
  
def gojo(a,b):
  if b > a:
    a, b = b, a
  c = a % b
  if c == 0:
    return(b)
  else:
    return gojo(b, c)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#import sys

#input = sys.stdin.readline

#import heapq
import math
import fractions

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

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=2
    k=1

    count=1
    if a>b:
        a,b=b,a
    sosu=set()
    #d = math.gcd(a,b)
#    print(d)
    c=math.sqrt(a)+1
    while m<c:
        if a%m==0:
            sosu.add(m)
            while a%m==0:
                a//=m

        m+=1

 #   print(sosu)
    for i in sosu:
        if b%i==0:
            count+=1



    print(count)
#    for i in range(h):
#            print(aaa)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数を２つのグループに分ける

import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = [1]
  fac = facto(c, fac)
  # print(fac)
  print(len(fac))  
  
def facto(n, fac):
  if n == 1:
    return [1]
  if n == 2:
    return[2]
  if n % 2 == 0:
    fac = [2]
  else:
    fac = []
  
  max_n = int(n ** 0.5 + 2)
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 1):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n //= cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
      
  return fac
  
def gojo(a,b):
  if b > a:
    a, b = b, a
  c = a % b
  if c == 0:
    return(b)
  else:
    return gojo(b, c)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    ls = [True] * (int(max(a, b) ** 0.5) + 1)
    ls[0] = False
    ls[1] = False
    p = [1]
    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
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

Solution code:
A, B = sorted([int(i) for i in input().split()])

res = 1
for i in range(2, int(B**0.5)+1):
    if B % i == 0:
        if A % i == 0:
            for j in range(2, int(i**0.5)+1):
                if i % j == 0:
                    break
            else:
                res += 1
        t = B // i
        if t != i and A % t == 0:
            for j in range(2, int(t**0.5)+1):
                if t % j == 0:
                    break
            else:
                res += 1

print(res)

Submission status: Wrong Answer

Solution code:
import math
import fractions
import itertools

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

A, B = [int(i) for i in input().split()]
a = make_divisors(A)
b = make_divisors(B)
c = set(a) & set(b)
C = list(c)

ans = 0
D = []
for x, y in itertools.combinations(C, 2):
    if x == 1 or y == 1:
        continue
    if fractions.gcd(x, y) == 1:
        D.append(x)
        D.append(y)
D.append(1)
E = set(D)
print(len(E))

Submission status: Wrong Answer

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

g = fractions.gcd(A,B)

cnt = 0
first = True
if math.sqrt(g) % 1 == 0:
    cnt += 1
    end = int(math.sqrt(g))
else:
    end = int(math.sqrt(g))+1


for i in range(2,end):
    while g%i == 0:
        g //= i
        if first:
            cnt += 2
            first = False

    first = True


print(cnt+1)

Submission status: Wrong Answer

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

g = fractions.gcd(A,B)

cnt = 0
first = True
if math.sqrt(g) % 1 == 0:
    cnt += 1
    end = int(math.sqrt(g))
else:
    end = int(math.sqrt(g))+1
  

for i in range(2,end):
    print(i,g%i)
    while g%i == 0:
        g //= i
        if first:
            cnt += 2
            first = False

    first = True


print(cnt+1)