Блог пользователя Caramelio

Автор Caramelio, история, 5 лет назад, По-английски

Do you think there are problems in Codeforces that are unsolvable with some type of programming languages?

For example, Python 3. The problem is

Alice and Bob play different games. When Alice plays, she always wins exactly a points. When Bob plays, he always wins exactly b points. Today, after they finished playing, they noticed they had the same number of points. What is the smallest number this could be?

Input The first line contains two integers, a and b, separated by spaces, where a is the number of points Alice wins in one game and b is the number of points Bob wins in one game.

Output You should return the smallest possible number of points that Alice and Bob have, which should be an integer c.

Examples input : 2 3 output: 6

input : 4 6 output: 12

Note Constraints:

1 ≤ a ≤ 10, 000

1 ≤ b ≤ 10, 000

1 ≤ c ≤ 100, 000, 000

When I solved this with Python 3, it couldn't solve it within the limit time. (1 second) Do you think I should create a program with C++, or am I not trying hard enough?

  • Проголосовать: нравится
  • -30
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

answer to the problem is lcm(a,b).

Relationship between hcf and lcm is ----> a*b = gcd(a,b) * lcm(a,b).

So if gcd is known , lcm can be calculated. GCD is calculated in logarithmic complexity and is very fast. Also If I remember correctly ; there is an inbuilt function in python3 which calculates gcd. So overall ; you should not be getting a TLE with pyhton3 for above problem if I am not wrong...