ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「スクエア・カルテット」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

2つの自然数の組 (a, b) が与えられたとき、自然数 x, y に関する次の方程式を考えます。

    x2 + a2 = y2 + b2 … (※)

例えば、(a, b) = (3, 10) のとき、方程式(※)の解は (x, y) = (10, 3), (46, 45) の 2 組です。

自然数の組 (a, b) に対し、方程式(※)の全ての解の x + y の和を F(a, b) と定義します。

例えば F(3, 10) = 10 + 3 + 46 + 45 = 104 です。

同様に、F(10, 50) = 3500、F(20, 100) = 15022 となることが確かめられます。

標準入力から、半角空白区切りで 2 つの自然数 a, b(1 ≦ a < b ≦ 105)が与えられます。
標準出力に F(a, b) の値を出力するプログラムを書いてください。

方針

与えられた a, b に対し、等式を成立させる整数解を求める問題です。

単純な解法としては、y = √(x2 + a2 – b2) と変形するやり方が考えられます。x の値を一つ選び、x2 + a2 – b2 の値が平方数になるかどうかをチェックするというやり方です。

ただこの方法はあまり高速ではありません。x の値の取り得る範囲が広すぎるためです。y ≦ x – 1 でなくてはなりませんから、上の y の式に代入すると、√(x2 + a2 – b2) ≦ x – 1 となります。両辺を 2 乗して整理すると、x ≦ (b2 – a2 + 1) / 2 という条件が得られます。a < b ≦ 105 という条件では、調べるべき範囲が膨大になり、多くの計算量を要してしまいます。

そこで、本問のポイントは、次の式変形を行うことです。

    (x + y) (x - y) = b2 - a2

変数 x, y を左辺に集めて因数分解しました。このように、整数に関する問題では、与式を因数分解した形で表すと道筋が見えてくることが多いです。さて、この式をじっと見てみると、x + y と x – y の積が b2 – a2 に等しいと分かります。つまり、b2 – a2 の約数が分かれば、それがx + y または x – y の候補になるということです。

b2 – a2(以下、K とします)の約数を求めるコードを書きましょう。割る数 d を 1 から始めて 1 ずつ増やしながら、K を割り切るかどうか確かめればOKです。なお、d を K までループさせる必要はありません。d が K の約数なら K / d も K の約数であるという事実を利用しましょう。d を √K までループさせれば十分です。また x と y がちゃんと整数になるかどうかも忘れずチェックしましょう。コードは次のようになります(C++)。

#include <iostream>
#include <vector>
using namespace std;

long long Sqrt(long long n) {
long long s, t;
if (n > 1;
} while (s < t); return t; } // nの約数の一覧を返す関数 vector<long long> Divisors(long long n) { long long s = Sqrt(n); vector<long long> v; for (long long i = 1; i > a >> b;
long long answer = 0;
long long z = b * b – a * a;
vector<long long> v = Divisors(z);
for (int i = 0; i < v.size(); i++) { long long p = v[i], q = z / v[i]; if ((p + q) % 2 != 0 || p = t: break return t def divisors(n): s = sqrt(n) v = set() for i in range(1, s+1): if n % i != 0: continue v.add(i) v.add(n / i) return v a, b = map(int, raw_input().split()) v = divisors(b + a) u = divisors(b - a) w = set() answer = 0 for p in v: for q in u: w.add(p * q) for p in w: q = (b * b - a * a) / p if (p + q) % 2 != 0 or p

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。