Problem:


幾何問題を解こう

A君は今日も幾何の問題を解いている。
幾何の問題を解く時は浮動小数点誤差に気をつけることが大事である。

浮動小数点誤差とは、2進法の有限小数で数を表す際におこる丸めによって起きる誤差である。
例えば、10進法での 0.1 は2進法では 0.00011001100110011 ... という無限小数になるが、
これを有限の桁で丸める際に誤差が発生してしまう。

正の整数 p, q が10進法で与えられる。
有理数 p / q を有限桁数の小数で表現することができるような b 進法（b は2以上の整数）を求めよ。
複数ある場合は最も小さいものを出力せよ。

Constraints

0 

Input Format

入力は以下の形式で標準入力から与えられる。

p q

Output Format

答えを一行に出力せよ。

Sample Input 1

1 2

Sample Output 1

2

1/2 は 2 進法で 0.1 です

Sample Input 2

21 30

Sample Output 2

10

21/30 は 10 進法で 0.7 です



Sample input:
1 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
import math
f=lambda n:min(int(i) for i in (round(n**(1/i),10) for i in range(1,int(math.log(n,2))+2)) if int(i)==i)
p,q=map(int,input().split())
if f(q)==q:
    e=math.gcd(p,q)
    q/=e
e=f(q)
if f(q)!=q:
    q/=e
print(int(q))

Submission status: Wrong Answer

Solution code:
import math
f=lambda n:min(int(i) for i in (round(n**(1/i),10) for i in range(1,int(math.log(n,2))+2)) if int(i)==i)
p,q=map(int,input().split())
if f(q)==q:
    e=math.gcd(p,q)
    q/=e
e=f(q)
if f(q)!=q:
    q=e
print(int(q))

Submission status: Wrong Answer

Solution code:
from fractions import gcd

if __name__ == "__main__":
    p, q = map(int, input().split())
    print(q//gcd(p, q))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from math import sqrt

if __name__ == "__main__":
    p, q = map(int, input().split())
    ans = q / gcd(p, q)
    while True:
        if sqrt(ans).is_integer():
            ans = int(sqrt(ans))
        else:
            print(ans)
            break

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from math import sqrt

if __name__ == "__main__":
    p, q = map(int, input().split())
    ans = q / gcd(p, q)
    while True:
        if sqrt(ans).is_integer():
            ans = int(sqrt(ans))
        else:
            print(int(ans))
            break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
p, q = map(int, input().split())
ret = q
for b in range(1, 100000):
    if b ** 1000 * p % q == 0:
        ret = min(ret, b)
print(ret)

Submission status: Wrong Answer

Solution code:
#import math
p, q = map(int, input().split())
#g = math.gcd(p, q)
#p //= g
#q //= g
ret = q
for b in range(1, 40000):
    if b ** 1000 * p % q == 0:
        ret = min(ret, b)
print(ret)

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

p, q = map(int, input().split())
g = gcd(p, q)
p //= g
q //= g
ret = q
for b in range(1, 40000):
    if b ** 1000 * p % q == 0:
        ret = min(ret, b)
print(ret)

Submission status: Wrong Answer

Solution code:
import math
p,q = map(int,input().split())
g = math.gcd(p,q)
print(q//g)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    while True:
        p,q = LI()
        g = fractions.gcd(p,q)
        rr.append(q//g)

        break



    return '\n'.join(map(str, rr))


print(main())

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    while True:
        p,q = LI()
        g = fractions.gcd(p,q)
        rr.append(max(q//g,2))

        break



    return '\n'.join(map(str, rr))


print(main())

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        p,q = LI()
        g = fractions.gcd(p,q)
        t = q//g
        k = 1
        while t % 4 == 0:
            k *= 2
            t //= 4
        for i in range(3,int(math.sqrt(t))+2,2):
            ii = i**2
            while t % ii == 0:
                k *= i
                t //= ii
        rr.append(t*k)

        break



    return '\n'.join(map(str, rr))


print(main())

Submission status: Wrong Answer

Solution code:
prime = [2]
def check(x):
    for i in prime:
        if x % i ==0:
            return False
        elif x < i * i:
            break
    return True

def set():
    for i in range(3,10**5,2):
        if check(i):
            prime.append(i)


set()
#print(prime)
p,q = [int(i) for i in input().split(' ')]

for i in prime:
    while True:
        if p % i ==0 and q % i == 0:
            p = p//i
            q = q//i
        else:
            break

print(q)

Submission status: Wrong Answer

Solution code:
prime = [2]
def check(x):
    for i in prime:
        if x % i ==0:
            return False
        elif x < i * i:
            break
    return True

def set():
    for i in range(3,10**5,2):
        if check(i):
            prime.append(i)


set()
#print(prime)
p,q = [int(i) for i in input().split(' ')]

for i in prime:
    while True:
        if p % i ==0 and q % i == 0:
            p = p//i
            q = q//i
        else:
            break
ans = 1
for i in prime:
    if q % i == 0:
#        print(q,i)
        q = q // i
        ans *= i
        while q % i ==0:
            q = q // i
            

    

print(ans)

Submission status: Wrong Answer

Solution code:
prime = [2]
def check(x):
    for i in prime:
        if x % i ==0:
            return False
        elif x < i * i:
            break
    return True

def set():
    for i in range(3,10**5,2):
        if check(i):
            prime.append(i)


set()
#print(prime)
p,q = [int(i) for i in input().split(' ')]

for i in prime:
    while True:
        if p % i ==0 and q % i == 0:
            p = p//i
            q = q//i
        else:
            break
ans = 1
for i in prime:
    if q % i == 0:
#        print(q,i)
        q = q // i
        ans *= i
        while q % i ==0:
            q = q // i
            
ans *= q
    

print(ans)

Submission status: Wrong Answer

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

g = gcd(p,q)
q//=g
print(q)

Submission status: Time Limit Exceeded

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

g = gcd(p,q)
q//=g

prime=[]
p=2
while p<q:
    if q%p==0:
        prime.append(p)
        q//=p
    else:
        p+=1
if q!=1:
    prime.append(q)
prime=set(prime)
if len(prime)==0:
    print(q)
else:
    res=1
    for p in prime:
        res*=p
    print(res)

Submission status: Accepted

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

if __name__=="__main__":
    a,b=map(int,input().split())
    b//=gcd(a,b)
    a,c=2,1
    while a**2<=b:
        if b%a==0:
            c*=a
            while b%a==0: b//=a
        a+=1
    print(c if b==1 else c*b)

Submission status: Accepted

Solution code:
import fractions
a,b=map(int,input().split())
b//=fractions.gcd(a,b)
a,c=2,1
while a**2<=b:
    if b%a==0:
        c*=a
        while b%a==0: b//=a
    a+=1
print(c*b)

Submission status: Accepted

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

a,b=map(int,input().split())
b//=gcd(a,b)
a,c=2,1
while a*a<=b:
    if b%a==0:
        c*=a
        while b%a==0:b//=a
    a+=1
print([c*b,c][b==1])

Submission status: Accepted

Solution code:
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n
p, q = map(int, input().split())
q //= gcd(p, q)

x = q; y = 1; k = 2
while k*k <= x:
    if x % k == 0:
        while x % k == 0: x //= k
        y *= k
    k += 1
y *= x

print(y)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        p,q = LI()
        g = fractions.gcd(p,q)
        t = q//g
        k = 1
        if t % 2 == 0:
            k *= 2
            while t % 2 == 0:
                t //= 2
        for i in range(3,int(math.sqrt(t))+2,2):
            if t % i > 0:
                continue
            k *= i
            while t % i == 0:
                t //= i
        rr.append(t*k)

        break



    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
prime = [2]
def check(x):
    for i in prime:
        if x % i ==0:
            return False
        elif x < i * i:
            break
    return True

def set():
    for i in range(3,10**5,2):
        if check(i):
            prime.append(i)


set()
#print('ok')
#print(prime)
p,q = [int(i) for i in input().split(' ')]
if q % p == 0:
    q = q //p
    p = 1
for i in prime:
    while True:
        if p % i ==0 and q % i == 0:
            p = p // i
            q = q // i
            #print(p,q,i)
        else:
            break
 
ans = 1
#print(p,q)
for i in prime:
    if q % i == 0:
#        print(q,i)
        q = q // i
        ans *= i
        while q % i ==0:
            q = q // i
            
ans *= q
    

print(ans)

Submission status: Accepted

Solution code:
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    p,q=map(int,input().split())
    g=math.gcd(p,q)

    p//=g
    q//=g

    
    
    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []
    
        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)
    
        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break
    
            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0
    
        return [prime for prime in prime_list if prime != 0]
    
    
    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""
    
        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)
    
            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452
    
            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1
    
            return dict_counter

    d=prime_factorization_2(q)
    ans=1
    for k in d.keys():
        ans*=k
    print(ans)
resolve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    while 1:
        n,m = LI()
        if n == 0 and m == 0:
            break
        v = [[] for i in range(n)]
        for i in range(m):
            a,b = LI()
            a -= 1
            b -= 1
            v[a].append(b)
            v[b].append(a)
        bfs_map = [1 for i in range(n)]
        bfs_map[0] = 0
        f = [0 for i in range(n)]
        q = deque()
        q.append(0)
        fl = 1
        while q:
            if not fl:break
            x = q.popleft()
            for y in v[x]:
                if bfs_map[y]:
                    bfs_map[y] = 0
                    f[y] = (1-f[x])
                    q.append(y)
                else:
                    if f[y] == f[x]:
                        print(0)
                        fl = 0
                        break
        if fl:
            ans = []
            k = sum(f)
            if k%2 == 0:
                ans.append(k//2)
            k = len(f)-sum(f)
            if k%2 == 0:
                ans.append(k//2)
            ans = list(set(ans))
            ans.sort()
            print(len(ans))
            for i in ans:
                print(i)
    return

#B
def B():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)

    def factorize(n):
        if n < 4:
            return {n:1}
        i = 2
        d = defaultdict(int)
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m//=i
                    d[i] += 1
            i += 1
        d[m] += 1
        return d
    p,q = LI()
    g = gcd(p,q)
    ans = q//g
    if ans == 1:
        print(1)
    else:
        d = factorize(ans)
        ans = 1
        for i in d.keys():
            ans *= i
        print(ans)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
import math
p,q=map(int,input().split())
q//=math.gcd(p,q)
i=2
a=1
while i*i<=q:
    if q%i==0:
        a*=i
        while q%i==0:
            q//=i
    i+=1
print(a*q)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
p, q = map(int, input().split())
g = math.gcd(p, q)
p, q = p // g, q // g;
ret = q
for b in range(1, 40000):
    if b ** 1000 * p % q == 0:
        ret = min(ret, b)
print(ret)

Submission status: Runtime Error

Solution code:
import math
p, q = map(int, input().split())
g = math.gcd(p, q)
p //= g
q //= g
ret = q
for b in range(1, 40000):
    if b ** 1000 * p % q == 0:
        ret = min(ret, b)
print(ret)

Submission status: Runtime Error

Solution code:
import math

p = int(input())
q = int(input())

print(b/(math.gcd(p,q)))

Submission status: Runtime Error

Solution code:
import math

p = int(input())
q = int(input())

print(q/(math.gcd(p,q)))

Submission status: Runtime Error

Solution code:
import math

p = int(input())
q = int(input())

print(int(q/(math.gcd(p,q))))

Submission status: Runtime Error

Solution code:
import math

def main():
     p = int(input())
     q = int(input())
     print(int(q/math.gcd(p,q)))

main()

Submission status: Runtime Error

Solution code:
import math

p = int(input())
q = int(input())
print(int(q/math.gcd(p,q)))