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: Runtime Error

Solution code:
import sympy
A,B = map(int,input().split())
print(1 + len(set(sympy.factorint(A).keys()) & set(sympy.factorint(B).keys())))

Submission status: Runtime Error

Solution code:
def is_prime(x):
    if x < 2: return False 
    if x == 2 or x == 3 or x == 5: return True 
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False 
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

a, b = (int(i) for i in input().split())
kouyaku = 0
for i in range(1,min(a,b)+1):
    if (a% i == 0) and (b%i==0):
        if i == 1:
            kouyaku += 1

        elif is_prime(i) == True:
            kouyaku+= 1
print(kouyaku)

Submission status: Runtime Error

Solution code:
from sys import stdin
import math

A, B = [int(x) for x in stdin.readline().rstrip().split()]
gcd = math.gcd(A, B)

x = 2
ans = 1
g = 1

while gcd > 1:
    if gcd % x == 0:
        gcd //= x
        if g != x:
            ans += 1
        g = x
    else:
        x += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import os
import math
A, B = map(int,input().split())
gcdAB = math.gcd(A,B)
P = []
for i in range(2,gcdAB):
    if gcdAB%i==0:
        P.append(i)
        gcdAB /=i
    i+=2
cnt =1
for p in P:
    if p!= 0:
        cnt +=1
print(cnt)

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(2000000000)
a,b= list(map(int, input().split()))
ma=math.gcd(a,b)
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 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
ans=1
for i in make_divisors(ma):
    if is_prime(i):
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())

from fractions import gcd
a = gcd(n,m)

import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

t = seachPrimeNum(10*8)
for item in t:
    if a % item == 0:
        c += 1

print(c)

Submission status: Runtime Error

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


if __name__ == '__main__':
    slove()

Submission status: Runtime Error

Solution code:
import math
a,b= list(map(int, input().split()))
ma=math.gcd(a,b)
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 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
ans=1
for i in make_divisors(ma):
    if is_prime(i):
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import math
from collections import Counter

def read():
    return int(input())

def readmap():
    return map(int, input().split())

def readlist():
    return list(map(int, input().split()))

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

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

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


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__":
    a, b = readmap()
    g = math.gcd(a, b)

    c = Counter(prime_factorize(g))

    print(len(c) + 1)

Submission status: Runtime Error

Solution code:
import math
import sys
input = sys.stdin.readline
A, B = map(int, input().split())

gcdv = math.gcd(A, B)

def fac(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

ans = len(fac(gcdv))
if ans == 1:
    print(1)
else:
    print(ans+1)

Submission status: Runtime Error

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    A,B = LMIIS()
    import math
    g = math.gcd(A,B)
    cds = set([1])
    d = 2
    while g != 1:
        if g % d == 0:
            g //= d
            cds.add(d)
        else:
            d += 1
    print(len(cds))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


if __name__ == '__main__':
    slove()

Submission status: Runtime Error

Solution code:
# ABC141d
import sys
import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

a, b = map(int, input().split())
cd = []
for i in range(1, math.gcd(a, b) + 1):
    if (a % i != 0 or b % i != 0):
        continue
    flag = True
    for j in cd:
        if (j == 1):
            continue
        if (i % j == 0):
            flag = False
            break
    if (flag):
        cd.append(i)
print(len(cd))

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
# from fractions import gcd

input = sys.stdin.readline

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

n = gcd(A,B)

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

frl = factorization(n)
if frl[0][0]==1:
	ans = 1
else:
	ans = len(frl)+1
print(ans)

Submission status: Runtime Error

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


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

GCD = gcd(a,b)
count = 0
for prime in primes(GCD):
    if GCD % prime == 0:
        count += 1
print(count+1)

Submission status: Runtime Error

Solution code:
def gcd(n,m):
    while n:
        m,n = [n,m%n]
    return m

def prime(N):
    se = [0,0,1]+[1]*(N-2)
    n = 2
    while n ** 2 <= N:
        if se[n]:
            nn = 2*n
            while nn <= N:
                se[nn] = 0
                nn += n
        n += 1

    return [x for x in range(0,N+1) if se[x]]

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

S = gcd(A,B)

s = 1
for i in prime(S):
    hoge = 0
    while S % i == 0:
        hoge += 1
        S //= i
    if hoge:
        s += 1

print(s)

Submission status: Runtime Error

Solution code:
n=int(input())
hoge=list(map(int,input().split()))
huga=[0]*n
for i in range(n):
  huga[hoge[i]-1]=i+1
for i in huga:
  print(i,end=" ")
print(" ")

Submission status: Runtime Error

Solution code:
a,b=list(map(int, input().split()))
def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def md(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 coprime(a, b):
    return gcd(a, b) == 1

c = md(gcd(a,b))
c.sort()
if len(c)== 1:
    print(1)
else:
    count = 1
    d = c[0]
    for i in c[1:]:
        if coprime(d, i):
            d = d*i
            count += 1
        else:
            continue

print(count)

Submission status: Runtime Error

Solution code:
import math

a, b = map(int, input().split())
n = math.gcd(a, b)

count = 0
for i in range(2, n):
    if n % i == 0:
        while n % i == 0:
            n = n // i
        count += 1
    if i > n:
        break

print(count)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ELEM(array)  (sizeof (array) / sizeof *(array))
#define MOD 1000000007
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define GCD(a,b) __gcd(a,b)
#define LCM(a,b) a/__gcd(a,b)*b
typedef long long ll;
typedef pair<int,int> Pii;

bool prime(ll n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0) return false;
    }
    return true;
}

int main(){
    ll a,b;
    cin>>a>>b;
    ll n=GCD(a,b);
    ll m=n;
    int k=2;
    bool t=true;
    int ans=1;
    if(prime(n)){
        cout<<2;return 0;
    }
    while(n!=1){
        if(n%k==0){
            if(t) ans++;
            t=false;
            n/=k;
            continue;
        }
        t=true;
        k++;
    }
    cout<<ans;
    return 0;
}

Submission status: Runtime Error

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

A, B = list(map(int, input().split(' ')))
maxKouyaku = math.gcd(A, B)
#print(maxKouyaku)
if maxKouyaku == 1:
    print(1)
else:
    print(len(factorization(maxKouyaku)) + 1)

Submission status: Runtime Error

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


if __name__ == '__main__':
    slove()

Submission status: Runtime Error

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
a, b = map(int, input().split(' '))
gc = math.gcd(a, b)
r = []
r = factorization(gc)
if len(r) == 1:
    print(1)
else:
    print(len(r)+1)

Submission status: Runtime Error

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

c =fractions.gcd(a,b)
c2 = c
F = []
while c2%2==0:
    c2 //= 2
if c2<c:
    F.append(2)
f = 3
while f*f<=c2:
    while c2 %f ==0:
        c2//=f 
        if F[-1]<f:
            F.append(f)
    f += 2
if c2 !=1:
  F.append(c2)
#print(F)
print(len(F)+1)

Submission status: Runtime Error

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


if __name__ == '__main__':
    slove()

Submission status: Runtime Error

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

p=2
f={}
while p*2<=A:
    c=0
    while A%p==0:
    	A//=p
        c+=1
    if c>0: f[p]=c
    p+=1
if A>1: f[A]=1

print(len(f)+1)

Submission status: Runtime Error

Solution code:
import math
def pFactorize(num):
    factor_list = []
    for i in range(2, math.floor(math.sqrt(num))+ 1):
        if num % i == 0:
            factor_list.append([i,1])
            num //= i
        while num % i == 0:
            factor_list[-1][1] += 1
            num //= i
    if not num == 1:
        factor_list.append([num,1])
    return factor_list
a,b=[int(_) for _ in input().split()]
c=pFactorize(math.gcd(a,b))
print(len(c)+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from math import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = {}
for i in range(2, int(g**0.5 + 1)):
    while g % i == 0:
        ans[i] = ans[i] + 1 if i in ans else 1
        g //= i
if g != 1:
    ans[g] = 1
print(len(ans) + 1)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  a,b=LI()

  a=getPrimeList(a)
  b=getPrimeList(b)

  a=list(set(a))
  b=list(set(b))

  c=a+b
  c.sort()

  ans=1
  y=c[0]
  cnt=1
  for x in c[1:]:
    if x==y:
      cnt+=1
    else:
      y=x
      cnt=1

    if cnt==2:
      ans+=1

  return ans

# main()
print(main())

Submission status: Runtime Error

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

# def make_divisors(a, b):
#     n = min(a, b)
#     m = max(a, b)
#     import math
#     divisors = []
#     for i in range(1, int(math.sqrt(n)) + 1):
#         if n % i == 0: #割り切れるとき
#             if m % i == 0:
#                 divisors.append(i)
#             if i != n//i:
#                 if m % (n // i) == 0:
#                     divisors.append(n//i)
#     divisors.sort()
#     return divisors

# lst = make_divisors(A, B)
# print (lst)

a = min(A, B)
def primes(n):
    import math
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

prime_lst = primes(a)

count = 1
for i in prime_lst:
    if A % i == B % i == 0:
        count += 1

print (count)

Submission status: Runtime Error

Solution code:
from math import gcd

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

def solve():
  A, B = map(int, input().split())
  return len(set(prime_factorize(gcd(A, B)))) + 1

print(solve())

Submission status: Runtime Error

Solution code:
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

import math

a, b = map(int, input().split())
c=math.gcd(a, b)
d=prime_factorize(c)
count=0
before=0
for i in range(len(d)):
    if d[i]!=before:
        count+=1
    before=d[i]

print(count+1)

Submission status: Runtime Error

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

common_divisors = []
for n in range(1, int(max(A, B) ** 0.5) + 1):
    if (A % n == 0) & (B % n == 0):
        common_divisors.append(n)


# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0, n) if s[i] and i > 1]


Primes = eratosthenes(max(A, B) + 1)
Primes_set = set(Primes)

ans = 0
for cd in common_divisors:
    if cd in Primes_set:
        ans += 1

print(ans + 1)

Submission status: Runtime Error

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

import math
g = math.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

gg = prime_factorize(g)
print(len(list(set(gg))) + 1)

Submission status: Runtime Error

Solution code:
from math import gcd
a, b = [int(i) for i in input().split()]
c = gcd(a, b)

def d(x):
    i = 2
    e=[]
    while True:
        if x % i == 0:
            e.append(i)
            while x % i == 0:
                x //= i
        if i * i > x:
            break
        i+=1
    if x != 1:
        e.append(x)
    return e
print(len(d(c))+1)