I want to find a number that (with an input of 2 numbers) is a multiple of the biggest one while being a multiple of the smallest one if you add or subtract the GCD of both numbers. In other words:
val%max(x,y)==0 and ((val-gdc(x,y))%min(x,y)==0 or (val gdc(x,y))%min(x,y)==0)
For example: if I have 4 and 7, the value would be 7 as it is a multiple of 7 and if you add 1 (which is the gcd of 7 and 4) it becomes 8, which is a multiple of 4 I need a solution that doesn't make use of loops if possible, as my solution does work but is quite slow with big numbers:
from math import gcd
x,y=map(int,input().split())
def fun(x,y):
big=max(x,y)
small=min(x,y)
d=gcd(x,y)
val=big
while (val d)%small!=0 and (val-d)%small!=0:
val =big
return val
val=fun(x,y)
print(val)
CodePudding user response:
Here's a solution that doesn't use loops. I've benchmarked it against numbers with up to 10 thousand digits, and its still running in subsecond times.
from math import gcd
def solve(n, m):
n, m = max(n, m), min(n, m)
d = gcd(n, m)
p, q = n//d, m//d
a = pow( p, -1, q)
b = pow(-p, -1, q)
return n * min(a, b)
It will give a different (but still correct) solution in rare circumstances- returning 0
instead n
(the bigger number) when both are valid solutions.