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:

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)

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

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

    return arr

#import numpy as np

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

#print(factorization(a))
prime_a = factorization(a).append(1)
prime_b = factorization(b).append(1)
#print(prime_a, prime_b)
print(1+len(set(prime_a)&set(prime_b)))

Submission status: Runtime Error

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

import math
gcd = math.gcd(A,B)


div = []
for i in range(1,gcd+1):
    if gcd % i == 0:
        div.append(i)

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

count = 1
for i in range(len(div)):
    if prime_num_check(div[i]):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import math

divisor=[1]
stack=[]
#eiclidean algorithm
A,B=map(int,input().split())
p=max(A,B)
q=min(A,B)
int2=0
gcd=0
while True:
    int2=p%q
    if int2==0:
        gcd=q
        break
    else:
        p=q
        q=int2

stack.append(gcd)
for i in range(2,math.ceil(math.sqrt(gcd))+1):
    if gcd%i==0:
        p=gcd//i
        stack.append(p)
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

while len(stack)!=0:
    p=stack.pop()
    for x in divisor:
        if i%x==0 and x!=1:
            break
    else:
        divisor+=[p]


print(len(divisor))

Submission status: Runtime Error

Solution code:
import fractions
a,b = [int(i) for i in input().split()]

gcd = fractions.gcd(a,b)

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

l = make_divisors(gcd)

print(len([i for i in l if is_prime(i)]) +1)

Submission status: Runtime Error

Solution code:
import sys

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

import math
gcd = math.gcd(A,B)

if gcd == 1:
    print(1)
    sys.exit()

div = []
for i in range(1,gcd+1):
    if gcd % i == 0:
        div.append(i)

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

count = 1
for i in range(len(div)):
    if prime_num_check(div[i]):
        count += 1
print(count)

Submission status: Runtime Error

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

temp = fractions.gcd(a, b)

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

d = primes(temp)
ans = 1
for ele in d:
    if a%ele==0 and b%ele==0:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
# 190928 D
from math import gcd as bltin_gcd

if __name__ == "__main__":
    def coprime2(a, b):
        return bltin_gcd(a, b) == 1

    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    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
    A,B = list(map(int,input().split()))
    kotable = sorted(divisor(gcd(A,B)))
    N = len(kotable)
    while True:
        flg = True
        for i in range(0,N-1):
            for j in range(i+1,N,1):
                if coprime2(kotable[i],kotable[j]) == False:
                    kotable.remove(kotable[j])
                    N -= 1
                    flg = False
                    break
            if flg == False:
                break
        if flg == True:
            break
                    
    print(len(kotable))

Submission status: Runtime Error

Solution code:
#-------------------------------------------------------------------
# 約数を高速で列挙するコード(Python)
# https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56
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 is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False
 
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
 
    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)
 
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
 
        if y != n - 1 and t & 1 == 0:
            return False
 
    return True

#-------------------------------------------------------------------
#Python -3.4.x
from fractions import gcd
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
a,b = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

g=gcd(a,b)
#p('g ', g)
L=make_divisors(g)

#p( gcd(a,b) )
#p( L )

ans=1
for l in L:
	#if a%l==0 and b%l==0: ans+=1
	if is_prime(l): ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long A,B;

    cin >> A >> B;

    long long C;

    if(A>=B){
        C = A%B;
    }else{
        C = B%A;
    }

    long long count = 0LL;

    long long now = 0; 
    long long a = 2;

    vector<int> yakusu;
    while(C >= a*a){
        if(C%a == 0){
            if (a != now){
                count++;
                yakusu.push_back(a);
                now = a;
            }
            C /= a;
        }else{
            a++;
        }
    }

    if(std::count(yakusu.begin(), yakusu.end(), C) == 0) count++;

    count++;

    cout << count << endl;
    return 0;


}

Submission status: Runtime Error

Solution code:
import math

def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)
 
 
        i = 0
 
        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1
 
    return (prime_list)

A, B  = map(int, input().split())
#N = int(input())
mymax = math.gcd(A, B)

if A == 1 or B == 1:
    print(1)
else:
    mylist = sieve_of_eratosthenes(mymax)

    mylist.sort()
    #print(mylist)
    
    mycnt = 0
    myanslist = [1]
    for i in mylist:
        if A%i == 0 and B%i == 0:
            myanslist += [i]
            #print(i)
#print('myanslist =' , myanslist)

mycnt = 0
myflag = 0
for i in range(len(myanslist)-1):
    for j in range(i + 1, len(myanslist)):
        #print(i, j ,math.gcd(myanslist[j],myanslist[i]))
        if math.gcd(myanslist[j],myanslist[i]) != 1:
            myflag =1
            break
            
    mycnt += 1
if myflag == 1:
    print(mycnt)
else:
    print(mycnt+1)

Submission status: Runtime Error

Solution code:
import math

divisor=[1]
stack=[]
#eiclidean algorithm
A,B=map(int,input().split())
p=max(A,B)
q=min(A,B)
int2=0
gcd=0
while True:
    int2=p%q
    if int2==0:
        gcd=q
        break
    else:
        p=q
        q=int2

stack.append(gcd)
for i in range(2,math.ceil(math.sqrt(gcd))+1):
    if gcd%i==0:
        p=gcd//i
        stack.append(p)
        for x in divisor:
            if i%x==0 and x!=1:
                break
        else:
            divisor+=[i]

while len(stack)!=0:
    p=stack.pop()
    for x in divisor:
        if i%x==0 and x!=1:
            break
    else:
        divisor+=[p]


print(divisor)

Submission status: Runtime Error

Solution code:
import math
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())
C=max(A,B)
D=min(A,B)
lis=make_divisors(D)
lis.sort()
l=len(lis)
ans=[1]
j=1
for i in range(2,math.gcd(A,B)+1):
    if A % i == 0 and B % i == 0:
        j=i
        break

if j==1:
    print(1)
else:
    for i in range(l):
            if C%lis[i]==0 and pow(j,lis[i]-1,lis[i])==1:
                ans.append(lis[i])
    if C%j==0:
        ans.append(j)
    print(len(ans))

Submission status: Runtime Error

Solution code:



def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        print '\t',f
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f +=6
        return True  

def divisor(a,b):
    tab = [1]
    for i in range (2, min(a,b)):
        if (a%i == 0 and b%i == 0):
            tab.append(i)
    return tab

def separatePrime(tab):
    pr = []
    npr = []
    for i in tab:
        if (is_prime(i) or i == 1):
            pr.append(i)
        else:
            npr.append(i)
    return pr, npr

def finish(pr, npr):
    for i in npr:
        can = True
        j = 1
        while (can and j < len(pr)):
            if (i%pr[j] == 0):
                can = False
            j += 1
        if (can):
            pr.append(i)
    
    return (len(pr))

data = raw_input().split()
a,b = int(data[0]), int(data[1])
tab = divisor(a,b)

pr,npr = separatePrime(tab)

print finish(pr, npr)