蟻本の練習問題埋め2-6(1)

蟻本

ユークリッドの互除法

AOJ 0005 - GCD and LCM

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005
やるだけ

POJ 2429 - GCD & LCM Inverse

http://poj.org/problem?id=2429

問題

ある数aとｂが決まっていて、そのGCDとLCMが与えられる。
このときaとb(a

制約

GCD, LCM <= 2^63

解法

GCDをg, LCMをlとする。

  • a = a'g
  • b = b'g
  • a'とb'は互いに素

が成り立つ。
ab = gl
より、
a'b' = l/g
よって、l/gを素因数分解し、互いに素になるようにa'とb'の候補を全て試せば良い。
数字が大きいので、√nの素因数分解は無理で、ポラード・ローを用いる。
2^63来たらやばそうだけど、unsigned long longにしなくても通る。

POJ 1930 - Dead Fraction

http://poj.org/problem?id=1930

問題

循環小数が与えられる。
ただし、循環の周期は分からない。
この循環小数を表すものとして考えられる分数表記の内、分母が最小のものを求めよ。

制約

循環小数は、
0.dddd...
の形のみ
ddddは長さ1~9の文字列で全てが0であることはない

解法

英語が読みにくい。循環小数ってどこでいってるのだろう。あと制約の文もわかりにくい。
考えられる周期は最大9個なので全部試す。
周期が決まったら、よくある循環小数→分数の計算をやって約分するだけ。
その中で分母が最小のものが答え。
doubleでやるとやばそうなので整数で計算する。
計算途中で出てくる数値は最大18桁なのでlong longで足りる。