[programmers/CodingTest/Python]最大公倍数と最小公倍数

3987 ワード
coding test python programmers テキストリンク

問題の説明


2つの数を入力し、2つの数の最大公約数と最小公約数の関数を返し、解を完了します.アレイの先頭にある最大公約数、次に最小公約数を返します.例えば、2つの数3および12の最大承諾数は3であり、最小公倍数は12であるため、ソリューション(3、12)は[3、12]を返さなければならない.

せいげんじょうけん


2つの数は1以上1000000以下の自然数です.

I/O例

n	m	return
3	12	[3, 12]
2	5	[1, 10]

I/O例説明


I/O例#1
上記のように.
I/O例#2
自然数2と5の最大承諾数が1であり、最小公倍数が10であるため、[1,10]を返さなければならない.

方法


2つの数に分けられる数の全部分.このとき、除算数は一時配列に格納されます.最大公倍数は一時配列のすべての数を乗じて得られ、最小公倍数は一時配列の数の積を乗じて得られる.
最小公倍数が1の場合、分割はできません.したがって、一時配列は空の配列として保持されます.したがって、一時配列には、乗算に影響しない数の1が挿入されます.
  • を1で割ると、一時配列tmpに1を入れることを示す.
  • に分けられる全ての数を求めるために使用する変数curを1とする.
  • nが1より大きく、mが1より大きく、curがnより小さく、mのより小さい数でドアを回転させる.
    ->curが1増加します.
    ->nの場合、mはcurで除算され、
    -->tmpにcurを加えます.
    -->n,mはcurで割った値に更新される.
    -->curを1に更新します.
    ->離れなければ、次の繰り返しを行います.
  • の最大公倍数を格納する変数gcdと、最小公倍数を格納する変数lcmとを1とする.
  • tmpを巡るiにリクエスト.
    ->gcdにiを乗算します.
    • n*m*gcdを
  • lcmに格納します.
  • の答えを[gcd,lcm]として保存します.
  • の答えを返します.

    • solution.py

    def solution(n, m):
    tmp=[1]
    cur=1
    while n>1 and m>1 and cur<=min(n, m):
        cur+=1
        if n%cur==0 and m%cur==0:
            tmp.append(cur)
            n, m=n//cur, m//cur
            cur=1
        else:
            continue
    gcd, lcm=1, 1
    for i in tmp:
        gcd*=i
    lcm=n*m*gcd
    answer=[gcd, lcm]
    return answer
    (部分的)リバースエンジニアリングのNemoorphismio
    アルゴリズム...困難