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:
import fractions
import math

tmp = list(map(int,(input().split())))
a = tmp[0]
b = tmp[1]

#limit = fractions.gcd(a, b)
limit = min(fractions.gcd(a, b), int(math.sqrt(a)), int(math.sqrt(b)))
cnt = 0
for i in range(2, limit+1):
  flag = False
  while (a % i == 0) and (b % i == 0):
    a = a // i
    b = b // i
    flag = True
  if flag:
    cnt += 1

last = min(a, b)
flag = False
if (a % last == 0) and (b % last == 0) and last > 1:
  cnt += 1

   
print (cnt+1)

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
cnt = 0
if a >= b:
  A = b
else:
  A = a
print(A)
pn=[2]
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
pn.append(1)

for i in pn:
  if a%i ==0 and b%i == 0:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())
l, m=[], []

##約数列の作成
#aの約数列lの作成
for i in range(1, a+1):
  if a%i==0:
    l.append(i)
    
#bの約数列mの作成
for j in range(1, b+1):
  if b%j==0:
    m.append(j)

#約数列の結合
l.extend(m)
l = list(set(l))

#sw_aを用意
sw = [0 for idx in range(len(l))]

for x in range(len(l)):
  for y in range(x):
    if l[x]%l[y]==0:
      sw[x]+=1

cnt=0
for c in range(len(sw)):
  if sw[c]==1:
    cnt+=1

print(cnt+1)

Submission status: Wrong Answer

Solution code:
import itertools, fractions
A, B = map(int, input().split())
cd_list = []
if A >= B:
    cd_list = [n for n in range(1, B+1) if A%n==0 and B%n==0]
else:
    cd_list = [n for n in range(1, A+1) if A%n==0 and B%n==0]
prime_list = [1]
for i in range(len(cd_list)):
    if sum([fractions.gcd(cd_list[i], n) for n in cd_list[:i]]) == len(cd_list[:i]):
        prime_list.append(cd_list[i])
print(len(prime_list))

Submission status: Wrong Answer

Solution code:
import math
a,b=map(int,input().split())
l=[]
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0:
        an=0
        if i==2:an=1
        if i<2 or i&1==0 :an=0
        if pow(2,i-1,i)==1: an=1
        if an==1: l.append(i)
print(len(l)+1)

Submission status: Wrong Answer

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

from collections import defaultdict
import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = defaultdict(lambda : 0)
  #print(c)
  fac[1] = 1
  fac = facto(c, fac)
  #print(fac)
  keys = list((fac.keys()))
  print(len(keys))  
  
def facto(n, fac):
  if n == 1:
    return fac
  # cursor = 2
  sosu = calcSosu(n // 2)
  for cursor in sosu:
    if n % cursor == 0:
      fac[cursor] += 1
      
  return fac

def calcSosu(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
  
  
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 gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
a,b = map(int,input().split())
b = gcd(a,b)
c = 0
a = 0
for i in range(2,1000001):
    while b%i == 0:
        b /= i
        a = 1
    if a:
        c+=1
    a = 0
    if b == 1:
        break
print(c+1)

Submission status: Wrong Answer

Solution code:
import fractions as fra
a,b=map(int,input().split())
c=fra.gcd(a,b)
d=[[i,1] for i in range(0,1000000)]
e=[]
t=0
for i in range(2,1000000):
    if(d[i][1]==1):
        e.append(i)
        t=i
        while(t<1000000):
            d[t][1]=0
            t+=i
        t=0
cnt=0
for i in range(len(e)):
    if(c%e[i]==0):
        cnt+=1
        c=c//e[i]
print('{0}'.format(cnt+1))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

counter = 0

def euqlid(a, b):
    while(a % b != 0):
        k = a % b
        a = b
        b = k
    
    return b

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

if(B > A):
    tmp = B
    B = A
    A = tmp

minimum = euqlid(A, B)
lim = 1
while(lim * lim < minimum):
    lim += 1

lim2 = 1
for i in range(lim + 1):
    judge = True
    if(lim2 * lim2 < i + 1):
        lim2 += 1

    if(minimum % (i + 1) != 0):
        judge = False
    
    for j in range(lim2):
        if((i + 1) % (j + 1) == 0 and j != 0 and i != j and judge):
            judge = False
            break
    
    if(judge):
        counter+=1

print(counter)

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(min(a, b) ** 0.5) + 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
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

Solution code:
a,b = list(map(int, input().split()))
lst = []
for i in range(1, min(a, b)+1):
    if a%i==b%i==0 and i%2 != 0 and i%3 != 0 and i%5 != 0 and i%7 != 0:
        lst.append(i)
#print(lst)

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

ct = 5
for i in lst:
  if is_prime(i):
    ct += 1
print(ct)

Submission status: Wrong Answer

Solution code:
def so_check(common_div, num, append_list):
    for v in common_div[1:]:
        if num % v == 0:
            return
    else:
        append_list.append(num)
        # print(common_div)
        return

a, b = map(int, input().split())
a_div_list = [a]
b_div_list = [b]
common_div = [1]
for i in range(2, int(min(a, b) ** 0.5) + 1):
    # if map(lambda x: i % x == 0, common_div[1:])
    if a % i == 0 and b % i == 0:
        a_div = a // i
        b_div = b // i
        # print(a_div, b_div, i)
    else:
        continue

    so_check(common_div, i, common_div)
    if b % a_div == 0:
        so_check(common_div, a_div, a_div_list)
    if a % b_div == 0:
        so_check(common_div, a_div, b_div_list)

for v in sorted(a_div_list + b_div_list):
    so_check(common_div, v, common_div)

print(len(common_div))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
A, B = map(int, input().split())


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

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

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

    return arr


af = factorization(A)
bf = factorization(B)
print(af)
print(bf)
ans = 1
for afi in af:
    if afi in bf:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    A,B = map(int, input().split())
    M = [i for i in range(1,max(A,B)+1) if A%i==0 and B%i==0]
    N = reversed(M)
    count = 1
    for n in N:
        for m in M[1:]:
            if n % m == 0:
                break
        else:
            count += 1
    return count + 1

    

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
def main():
    def prime_table(n):
        list = [True for _ in range(n + 1)]
        list[0] = False

        for i in range(2, int(n ** 0.5) + 1):
            if list[i]:
                for j in range(i * 2, n, i):
                    list[j] = False
        return list[1:]

    def is_prime(n):
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    a, b = map(int, input().split())
    m = max(a, b)
    mx = int(m ** 0.5)

    tbl = prime_table(mx)

    ans = set()

    for p, bl in enumerate(tbl, 1):
        if a % p == 0 and b % p == 0:
            if bl:
                ans.add(p)
        if p != 0:
            if a % p == 0:
                qa = a // p
                if b % qa == 0 and is_prime(qa):
                    ans.add(qa)
            if b % p == 0:
                qb = b // p
                if a % qb == 0 and is_prime(qb):
                    ans.add(qb)

    print(len(ans))
    # print(*ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
if min(a,b) <=2 or (a % 2 ==0 or b % 2 == 0):
    if max(a,b) % 2 !=0:
        print(1)
        exit()
    else:
        print(2)
        exit()

comm = [1,2]
end = int(((max(a,b)) + 1)/2) + 1
if end >= min(a,b):
    end = min(a,b)+1

for i in range(3,end,2):
    if a % i ==0 and b % i == 0:
        flag1 = True
        for j in comm[1:]:
            if i <= j:
                flag1 = False
                break
            if i % j == 0:
                flag1 = False
                break
        if flag1:
            comm.append(i)

print(len(comm))

Submission status: Wrong Answer

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

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
while p*p <= MAXN:
    if sieve[p]:
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

ans = 1
for n,s in enumerate(sieve):
    if s:
        if A%n == B%n == 0:
            ans += 1

if ans==1 and A==B:
    print(2)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def isPrime(N, arr):
	if N == 1:
		return True
	for i, x in enumerate(arr):
		if x > 1 and N % x == 0:
			return False
	return True

def q_D(A, B):
	target = A
	another = B
	if A > B:
		target = B
		another = A
	yaku = []
	if target == 1:
		yaku.append(1)
	else:
		for i in range(int(target**0.5)+1):
			x = i + 1
			if target % x == 0 and another % x == 0:
				if isPrime(x, yaku):
					yaku.append(x)
	print(len(yaku))

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

Submission status: Wrong Answer

Solution code:
import math
import itertools

def gcd(x, y):
    if y == 0:
        #print("if conditional")
        return x
    else:
        #print("else conditional")
        return gcd(y, x % y)

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()]
#print(A, B)
a = make_divisors(A)
b = make_divisors(B)
c = set(a) & set(b)
C = list(c)
#print(c)

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

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    x1, x2 = map(int, input().split())
    if x1 == 1 or x2 == 1:
        print(1)
    else:
        cf = []

        divisors1 = []
        for i in range(1, int(x1 ** 0.5) + 1):
            if x1 % i == 0:
                divisors1.append(i)
                if i != x1 // i:
                    divisors1.append(x1 // i)

        divisors2 = []
        for j in range(1, int(x2 ** 0.5) + 1):
            if x2 % j == 0:
                divisors2.append(j)
                if j != x2 // j:
                    divisors2.append(x2 // j)
        # print(divisors1)
        # print(divisors2)

        koyakusu = set(divisors1) & set(divisors2)
        koyakusu.remove(1)

        for k in list(koyakusu):
            appendable = True
            for m in cf:
                if k % m == 0:
                    appendable = False
                    break
            if appendable:
                cf.append(k)

        print(len(cf) + 1)

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
cf = []
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

for i in range(1, min(A, B) + 1):
  if A % i == 0 and B % i == 0:
    cf.append(i)
ans = set()
for i in range(len(cf)):
  j = i + 1
  for j in range(len(cf)):
    if coprime(cf[i], cf[j]) == True:
      ans.add(cf[i])
      ans.add(cf[j])
print(len(ans))

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
import math

def is_prime(n):
    if n == 1: return False

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

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

gcd_AB = gcd(A, B)
cd = []
for i in range(2, int(math.sqrt(max(A, B)))*2 ):
    if A % i == 0 and B % i == 0:
        cd.append(i)

count = 1
for i in range(len(cd)):
    if is_prime(cd[i]) == True:
        count += 1

print(count)

Submission status: Wrong Answer

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


def furui(data):
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


a, b = map(int, input().split())
# a, b = 100000000000000, 1000000000000000
a = make_divisors(a)
a = furui(a)
b = make_divisors(b)
b = furui(b)

ans = len(set(a) & set(b)) + 1
if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
'''連徐法を利用した別バージョン'''
A,B = map(int, input().split())

M = max(A,B)//2
# print(M)
CoP = set([1])
end_flg = 0
ccc = 0

for i in range(1,M,2):
    Co_flg = 1
#     print(i+1, A % (i+1), B % (i+1))
    while Co_flg:
        ccc +=1 
        
        if A % (i+1) == 0 and B % (i+1) == 0:
            CoP.add(i+1)
            A = A /(i+1)
            B = B /(i+1)
            if i > min(A,B)//2:
                end_flg = 1
                break
                
#             print(A,B)
        else:
            Co_flg = 0
    if end_flg == 1:
        break
    

# print(CoP)
print(len(CoP))
# print(ccc)

Submission status: Wrong Answer

Solution code:
# D - Disjoint Set of Common Divisors

import fractions
import math

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

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

div_list = []
div_list.append(1)
g = fractions.gcd(a, b)
for i in range(2, g//2+1):
    if g % i == 0:
        div_list.append(i)
div_list.append(g)

cnt = 1
for i in div_list:
    if isPrime(i) == True:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def coprime(a, b):
    return gcd(a, b) == 1

a_div = divisor(a)
b_div = divisor(b)
a_div.sort()
b_div.sort()

ps = []

for aa in a_div:
    if aa in b_div:
        ps.append(aa)
ps.sort()


ans = 0
cnt = 0
# for v in itertools.combinations(ps, 2):
#     cnt += 1
#     print(v)
#     x = v[0]
#     y = v[1]
#     if coprime(x,y):
#         ans += 1
# print(cnt)
for i in range(len(ps)):
    for j in range(i,len(ps)-i):
        x = ps[i]
        y = ps[i]
        if coprime(x,y):
            ans += 1
print(ans)

# print(len(ps))

#1000000000000



#公約数を求める
# 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

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

A, B = map(int, input().split())
n = int(np.sqrt(min(A, B)))
a = []
Ans = []
tem = 0

for i in range(n):
    if A % (i + 1) == 0 and B % (i + 1) == 0:
        a.append(i + 1)
        if A % (A // (i + 1)) == 0 and B % (A // (i + 1)) == 0:
            a.append(A // (i + 1))

a = np.sort(a)
b = copy.copy(a)

if len(a) == 2:
    print(1)

else:
    for j in range(len(a) - 1):
        tem = a[j + 1]
        for k in range(j + 2, len(a)):
            if a[k] % a[j + 1] == 0:
                b[k] = 0

    for l in range(len(b)):
        if b[l] != 0:
            Ans.append(b[l])

    print(len(Ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from math import sqrt

a,b = [ int(x) for x in sys.stdin.readline().strip().split() ]
c=1
if a==b:
    f= True
    for i in range(2,int(sqrt(a))+1):
        if a%i==0:
            f= False
            break
    #
    if f: c+=1
else:
    n = int(sqrt(min(a,b)))
    p= { i for i in range(2,n+1) }
    for i in range(2,n+1):
        if not i in p: continue
        p-= { j for j in range(i+i,n+1,i) }
    #
    for pi in p:
        if a%pi==0 and b%pi==0: c+=1#
        
print(c)

Submission status: Wrong Answer

Solution code:
A,B = map(int,input().split())
c = 1
for i in range(2,A+1):
    for j in range(2, B+1):
        if i % j == 0:
            if i == j:
                c +=1
            else:
                break
print(c)

Submission status: Wrong Answer

Solution code:
import fractions

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

G = fractions.gcd(A, B)
ans = 1

for i in range(G-1):
    if (G < i):
        break
    if(G % (i+2) == 0):
        ans += 1
        j = 1
        while(G % ((i+2)**j) == 0):
            G /= i+2
            j += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys

#input = sys.stdin.readline

#import heapq
import math

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

    c = math.sqrt(max(a, b))


    m = 2

    if a % m == 0 and b % m == 0:
        count += 1
        while True:
            a //= m
            b //= m
            if a % m == 0 and b % m == 0:
                continue
            else:
                break
        c = math.sqrt(max(a, b))
    elif a % m == 0:
        a //= m
        c = math.sqrt(max(a, b))
    elif b % m == 0:
        b //= m
        c = math.sqrt(max(a, b))
        
    while m < c:
        m = 2 * k +1
        if a % m == 0 and b % m == 0:
            count += 1
            while True:
                a//=m
                b//=m
                if a%m==0 and b%m==0:
                    continue
                else:
                    break
            c=math.sqrt(max(a,b))
        elif a%m==0:
            a//=m
            c=math.sqrt(max(a,b))
        elif b%m==0:
            b//=m
            c=math.sqrt(max(a,b))
 #           print(count)
        k += 1




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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import fractions
import math

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

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 = map(int, input().split())
g = fractions.gcd(a, b)
if is_prime(g):
  print(2)
  exit()

l = make_divisors(g)
count = 0
for e in l:
  if is_prime(e):
    count += 1
print(count)

Submission status: Wrong Answer

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

factor = []
for i in range(2, greatest):
    while greatest % i == 0:
        greatest //= i
        factor.append(i)
factor = set(factor)
print(len(factor) + 1)

Submission status: Wrong Answer

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

def trial_division(target):
    dest = int(math.sqrt(target))
 
    for i in range(2,dest):
        if target % i == 0:
            return True
    return False

if a < b:
    a, b = b, a
while a % b != 0:
    a, b = b, a % b
gcd = b

if trial_division(gcd):
    print(2)
    sys.exit()

i = 2
result = 1
while True:
    if gcd % i == 0:
        while gcd % i == 0:
            gcd = gcd / i
        result += 1
    else:
        i += 1
    if i > gcd:
        break  
        
print(result)

Submission status: Wrong Answer

Solution code:

A,B =map(int,input().split())
if A<B:
    A,B =B,A
foo = 1
while foo != 0:
    A,B = B, A%B
    #print(A,B)
    foo = B

foo =A

plis=[2];C=10**4
for L in range(3,C):
    chk=True
    for L2 in plis:
        if L%L2 == 0:chk=False
    if chk==True:plis.append(L)

ans = 1
for p in plis:
    if  foo % p ==0:
        ans += 1
        foo = foo//p
    while foo % p == 0:
        foo = foo//p

if foo==1:
    print(ans)
elif int(foo**0.5)**2 ==foo:
    print(ans+1)
else:
    print(ans+2)

Submission status: Wrong Answer

Solution code:
inp = input().split()
a = int(inp[0])
b = int(inp[1])
 
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)
 
  return divisors
 
def gcd(a, b):
  while b != 0:
    a, b = b, a % b
  return a
  
a_div = make_divisors(a)
b_div = make_divisors(b)
 
common_div = list(set(a_div) & set(b_div))
 
out = []
for i in range(len(common_div)):
  for j in range(len(common_div)):
    if j == i:
      continue
    if gcd(common_div[i], common_div[j]) != 1:
      out.append(max(common_div[i], common_div[j]))
      break
 
d = set(common_div).difference(set(out))
print(len(d))

Submission status: Wrong Answer

Solution code:
A,B=map(int,input().split())
# 公約数を求めて公約数について互いに素なものの個数を出力する
i=2
count=1  # 1は最初から互いに素な公約数
while (not (A==i or B==i)) and (A%i==0 and B%i==0):
    if A%i==0 and A%i==0:
        while A%i==0 and B%i==0:
            A=A//i
            B=B//i
        count+=1
    i+=1

print(count)

Submission status: Wrong Answer

Solution code:
  
import subprocess
import os
import time


import sys
import math
from fractions import gcd
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


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 check(n, ans):
    for v in n:
        if v in ans and v != 1:
            return False

    return True


def main():
    a, b = map(int, input().split())

    ans = []

    nums = make_divisors(gcd(a, b))
    nums.sort()

    for n in nums:
        if check(make_divisors(n), ans):
            ans.append(n)

    print(len(ans))

Submission status: Wrong Answer

Solution code:
#coding: utf-8
m,n = map(int,input().split())
# div = [0]
div = [1]
flg = 0
ans = 0
i = 1

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

while i <= m+1:
    if m % i == 0 and n % i == 0:
        ans += 1
        m = m / i
        n = n / i
    i += 1
# 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
#         # 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)))
# print(len(div))
print(ans)

Submission status: Wrong Answer

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)

    return divisors

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

listA = make_divisors(A)
listB = make_divisors(B)
lst = list(set(listA) & set(listB))

if len(lst) == 1:
    print(1)
else:
    check = [lst[1]]
    for i in range(1, len(lst)):
        for c in check:
            if lst[i] % c == 0:
                break
        else:
            check.append(lst[i])
    print(len(check)+1)

Submission status: Wrong Answer

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




import fractions
def common_divisors(a, b):
    a = fractions.gcd(a, b)
    divisors =  [d for d in range(2, a // 2 + 1) if a % d == 0] + [a]
    if not 1 in divisors:
        divisors.append(1) 
    return divisors, a

CommonDivs,_ = common_divisors(A, B)
from collections import deque
CommonDivs.reverse()
q = deque(CommonDivs)
ans = [q.pop()]
max_n = max(CommonDivs)
while len(q) > 0:
    a = q.pop()
    ans.append(a)
    if max_n/2 < a:
        break
    for _ in range(len(q)):
        b = q.pop()
        if b % a != 0:
            q.appendleft(b)
            
print(len(ans)+len(q))

Submission status: Wrong Answer

Solution code:
#import sys

#input = sys.stdin.readline

#import heapq
import math

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

    c = math.sqrt(max(a, b))
    while m < c:
        m = 2 * k +1
        if a % m == 0 and b % m == 0:
            count += 1
            while True:
                a//=m
                b//=m
                if a%m==0 and b%m==0:
                    continue
                else:
                    break
            c=math.sqrt(max(a,b))
        elif a%m==0:
            a//=m
            c=math.sqrt(max(a,b))
        elif b%m==0:
            b//=m
            c=math.sqrt(max(a,b))
 #           print(count)
        k += 1

    m=2


    if a % m == 0 and b % m == 0:
        count += 1
        while True:
            a //= m
            b //= m
            if a % m == 0 and b % m == 0:
                continue
            else:
                break
        c = math.sqrt(max(a, b))
    elif a % m == 0:
        a //= m
        c = math.sqrt(max(a, b))
    elif b % m == 0:
        b //= m
        c = math.sqrt(max(a, b))


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

s = []

for i in range(2,min(1+10**7,1+(max(A,B)-min(A,B))//2)):
  if A%i==0 and B%i==0:
    s.append(i)
#print(s)
k = 0

while s:
  t = s.pop(0)
  #print(t)
  c = 0
  for j,i in enumerate(s[:]):
    if i%t==0:
      s.pop(j-c)
      c+=1
  #print(s)
  k+=1
print(k+1)

Submission status: Wrong Answer

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

t = 0
def gcd(A, B):
    global t
    if A <= 1 or B <= 1:
        return 0
    if A > B:
        if A!=B:
            t+=A%(A-B) == 0 or B%(A-B)==0
        return gcd(A-B, B)
    else:
        if A!=B:
            t+=A%(B-A) == 0 or B%(B-A)==0
        return gcd(B-A, A)

print(t+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
A, B = map(int, input().split())


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

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

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

    return arr


af = factorization(A)
bf = factorization(B)
ans = 1
for afi in af:
    if afi in bf:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def isPrime(N, arr):
	if N == 1:
		return True
	for i, x in enumerate(arr):
		if x > 1 and N % x == 0:
			return False
	return True

def q_D(A, B):
	target = A
	another = B
	if A > B:
		target = B
		another = A
	yaku = []
	if target == 1:
		yaku.append(1)
	else:
		for i in range(int(target**0.5)):
			x = i + 1
			if target % x == 0 and another % x == 0:
				if isPrime(x, yaku):
					yaku.append(x)
	print(len(yaku))

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

Submission status: Wrong Answer

Solution code:
def common_divisor(a, b):
    # a <= b
    res = []
    for i in range(2, int(a**0.5)+1):
        if a % i == 0 and b % i == 0:
            res.append(i)
            t = a // i
            if i != t and b % t == 0:
                res.append(t)
    return sorted(res)

def primes_num(arr):
    res = 0
    for i in arr:
        flg = True
        rt_i = i**0.5
        for j in arr:
            if rt_i <= j:
                break
            elif i % j == 0:
                flg = False
                break
        if flg: res += 1
    return res

A, B = sorted([int(i) for i in input().split()])
# A <= B

cds = common_divisor(A, B)
print(primes_num(cds)+1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import math
input = sys.stdin.readline

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

check_list = [1]
if a % 2 == 0 and b % 2 == 0:
    check_list.append(2)

for i in range(3, 10 * 6, 2):
    aa = False
    bb = False
    if a % i == 0:
        aa = True
    if b % i == 0:
        bb = True

    if aa == True and bb == True:
        check_list.append(i)

# print(a_list)
# print(b_list)

ans = 0
for check in check_list:
    prime = True
    for i in range(2, int(math.sqrt(check))+1):
        if check % i == 0:
            prime = False
            break

    if prime == True:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    def prime_table(n):
        list = [True for _ in range(n + 1)]
        list[0] = False

        for i in range(2, int(n ** 0.5) + 1):
            if list[i]:
                for j in range(i * 2, n, i):
                    list[j] = False
        return list[1:]

    def is_prime(n):
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    a, b = map(int, input().split())
    m = max(a, b)
    mx = int(m ** 0.5)

    tbl = prime_table(mx)

    ans = set()

    for p, bl in enumerate(tbl, 1):
        if a % p == 0 and b % p == 0:
            if bl:
                ans.add(p)

            qa = a // p
            if b % qa == 0 and is_prime(qa):
                ans.add(qa)

            qb = b // p
            if a % qb == 0 and is_prime(qb):
                ans.add(qb)

    print(len(ans))
    # print(*ans)


if __name__ == '__main__':
    main()