プログラミングコンテストチャレンジブック 3-1

第3章 3-1 「数学的な問題を解くコツ」からです。

• ユークリッドの互除法で最大公約数を求める
  • 2つの格子点の間を結ぶ線分状にのる格子点の数を求めるのに平面ベクトルの x, y 要素の最大公約数を用いる
• 拡張ユークリッドの互除法
  • ax + by = 1 となる a, b を求める
• 素数判定
  • エラトステネスの篩
• 高速なべき乗計算
  • 繰り返し二乗法