poj 1061カエルのデート(拡張ユークリッドアルゴリズム)
1319 ワード
【テーマ】
poj 1061カエルのデート
【題意】
2匹のカエルは所定の長さの数軸上で運動し、所定の初期位置とジャンプの毎回の長さを与え、いつ2匹のカエルが出会うことができるかを尋ねた.
【考え方】
題意によりx+mt=y+nt+kl,tはジャンプ回数を表す.式x−y=(n−m)*t+k*lを変化させてax+by=cのような形にしたので,拡張ユークリッドアルゴリズムを用いて最小ジャンプ回数を求めることを考慮した.
【コード】
poj 1061カエルのデート
【題意】
2匹のカエルは所定の長さの数軸上で運動し、所定の初期位置とジャンプの毎回の長さを与え、いつ2匹のカエルが出会うことができるかを尋ねた.
【考え方】
題意によりx+mt=y+nt+kl,tはジャンプ回数を表す.式x−y=(n−m)*t+k*lを変化させてax+by=cのような形にしたので,拡張ユークリッドアルゴリズムを用いて最小ジャンプ回数を求めることを考慮した.
【コード】
#include
#include
#include
#include
#include
#include