数学的な問題線分上の格子点の個数ユークリッドの互除法蟻本読書会

ひとりで勝手にはじめた蟻本読書会グラフ理論木上での全頂点対最短経路問題と最小共通祖先蟻本読書会の続きです。

Contents

1 線分上の格子点の個数
2 最大公約数と最小公倍数
3 応用問題
4 拡張ユークリッド互除法

線分上の格子点の個数

点A（x1, y1）と点B（x2, y2）がある。線分AB上の格子点の数を求めよ。

この問題、簡単に答えを出す方法があります。問題を簡単にするために少し変えてみます。

点（x, y）がある。原点と点を結ぶ線分上の格子点の数を求めよ。

線分上の X 座標と Y 座標がともに整数となるのは x と y がそれぞれ同じ数で割り切れる場合です。そのため答えと x, y の最大公約数が関係しています。

x, y をそれぞれ最大公約数で割ったものが原点にもっとも近い格子点の X 座標と Y 座標となります。では格子点の数はどうなるでしょうか？原点と点（x, y）は求める格子点の数に含めない場合、（x, y の最大公約数 – 1）が答えになります。

そのため点A（x1, y1）と点B（x2, y2）を結ぶ線分上の格子点の数は |x1 – x2|と|y1 – y2|の最大公約数から1を引いたものとなります。ただし少なくとも片方が 0 になる場合、最大公約数を使う解法は使えないので注意が必要です。

最大公約数と最小公倍数

最大公約数を求める方法にユークリッドの互除法があります。

2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質があります。この性質を利用して、 b を r で割った剰余、除数 r をその剰余で割った剰余、と剰余を求める計算を繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となります。これによって最大公約数を求めようというのがユークリッドの互除法です。

long GCD(long a, long b)
{
    while (a != 0 && b != 0)
    {
        if (a < b)
            b = b % a;
        else
            a = a % b;
    }
    return Math.Max(a, b);
}

long GCD(long a, long b)

{

while (a != 0 && b != 0)

{

if (a < b)

b = b % a;

else

a = a % b;

}

return Math.Max(a, b);

}

再帰にすると少し短く書けます。

long GCD(long a, long b)
{
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}

long GCD(long a, long b)

{

if (b == 0)

return a;

else

return GCD(b, a % b);

}

最小公倍数は最大公約数から容易に算出できます。最小公倍数は 2つの積 ÷ 最大公約数です。複数の自然数の最大公約数や最小公倍数も最初に a と b の最大公約数や最小公倍数を求め、これと c の最大公約数や最小公倍数を求めることを繰り返すことで求めることができます。

C – Multiple Clocks

N 台の時計があり、i(1 ≦ i ≦ N) 番目の時計の針はちょうど T_i 秒で時計盤を 1 周します。最初、全ての時計の針は真っ直ぐ上に向いており、止まっています。
イルカは、全ての時計の針を同時に動かし始めました。
再び、全ての時計の針が真っ直ぐ上に向くのは何秒後でしょうか?

入力されるデータ
N
T_1
T_2
:
T_N

（ただし 1 ≦ N ≦ 100, 1 ≦ T_i ≦ 10^18）
答えは 10^18 以下であることが保証されている

T_1, T_2, … , T_N の最小公倍数を求める問題です。ただ最小公倍数を求める計算でオーバーフローしないように気をつけなければなりません。a * b / GCD(a, b) を計算しようとすると a * b が long型の範囲を超えてしまうかもしれません。

a, b の最大公約数は a, b と同じかそれよりも小さな値になるので、a / GCD(a, b) * b と割り算を先にしてオーバーフローを回避します。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    // 最大公約数
    static long GCD(long a, long b)
    {
        while (a != 0 && b != 0)
        {
            if (a < b)
                b = b % a;
            else
                a = a % b;
        }
        return Math.Max(a, b);
    }

    // 最小公倍数
    static long LCM(long a, long b)
    {
        return a / GCD(a, b) * b;
    }

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        long ans = 1;
        for (int i = 0; i < N; i++)
        {
            long value = long.Parse(Console.ReadLine());
            ans = LCM(ans, value);
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

// 最大公約数

static long GCD(long a, long b)

{

while (a != 0 && b != 0)

{

if (a < b)

b = b % a;

else

a = a % b;

}

return Math.Max(a, b);

}

// 最小公倍数

static long LCM(long a, long b)

{

return a / GCD(a, b) * b;

}

static void Main()

{

int N = int.Parse(Console.ReadLine());

long ans = 1;

for (int i = 0; i < N; i++)

{

long value = long.Parse(Console.ReadLine());

ans = LCM(ans, value);

}

Console.WriteLine(ans);

}

応用問題

A – Getting Difference

箱に N 個のボールが入っていて、i 番目のボールには整数 A_i が書かれている。

「箱から二つのボールを取り出し、その二つのボールに書かれている数の差の絶対値を書いた新しいボールと一緒に箱に戻す」という操作を好きな回数だけおこなうことができる。

これによって整数 K の書かれたボールが箱の中に入っている状態にできるかどうか判定せよ。できる場合には POSSIBLE、できない場合には IMPOSSIBLE と出力せよ。

入力されるデータ
N K
A_1 A_2 … A_N

（ただし、
1 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9
1 ≦ K ≦ 10^9 ）

これも最大公約数を使う問題です。

A_1, A_2, …, A_N のの最大値を M とし、これらの最大公約数を G とします。すると K と書かれたボールを箱に入れることができるための必要十分条件は、K が G で割り切れる M 以下の整数であることです。

まず、箱に追加するボールに書かれる数はふたつの数の差の絶対値なので、ふたつの数よりも大きな数には絶対になりません。なので M より K のほうが大きいと IMPOSSIBLE となります。なので「K が M 以下の整数」であることは自明です。

次にどんな操作をしても、箱の中のボールに書かれた数の最大公約数は G のままであり、最大値も M から変わることはありません。

二つのボールに書かれた差を取るという操作を繰り返すと、ユークリッドの互除法のような操作になります。これはある二つのボールの最大公約数のボールを箱に入れることが可能になることを意味しています。

そのため箱のなかには必ず G と書かれたボールを入れることができます。そのあとは、M と G の差を取ることを繰り返すことで、M, M – G, M – 2G, … 2G, G と書かれたボールはすべて箱に入れることができることがわかります。M, M – G, M – 2G, … 2G, G のなかに K があれば POSSIBLE となり、そうでないなら IMPOSSIBLE となります。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    // 最大公約数
    static long GCD(long a, long b)
    {
        while (a != 0 && b != 0)
        {
            if (a < b)
                b = b % a;
            else
                a = a % b;
        }
        return Math.Max(a, b);
    }

    static void Main()
    {
        int N, K;
        {
            int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            N = vs[0];
            K = vs[1];
        }
        int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        long max = values.Max();
        long gcd = values[0];
        for (int i = 1; i < N; i++)
        {
            long value = values[i];
            gcd = GCD(gcd, value);
        }

        // K が max 以下の整数
        // K が gcd で割り切れる
        if(K <= max && K % gcd == 0)
            Console.WriteLine("POSSIBLE");
        else
            Console.WriteLine("IMPOSSIBLE");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

// 最大公約数

static long GCD(long a, long b)

{

while (a != 0 && b != 0)

{

if (a < b)

b = b % a;

else

a = a % b;

}

return Math.Max(a, b);

}

static void Main()

{

int N, K;

{

int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

N = vs[0];

K = vs[1];

}

int[] values = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

long max = values.Max();

long gcd = values[0];

for (int i = 1; i < N; i++)

{

long value = values[i];

gcd = GCD(gcd, value);

}

// K が max 以下の整数

// K が gcd で割り切れる

if(K <= max && K % gcd == 0)

Console.WriteLine("POSSIBLE");

else

Console.WriteLine("IMPOSSIBLE");

}

拡張ユークリッド互除法

割り算から一次方程式の解を求める方法とユークリッドの互除法を応用させると、整数 A , B を用いた一次方程式 Ax + By = gcd(A, B) の整数解 x , y を求めることができます。この x , y を求めるアルゴリズムを拡張ユークリッドの互除法といいます。

拡張ユークリッドの互除法 (paizaランク C 相当)

整数 A , B が与えられるので、拡張ユークリッドの互除法を用いて Ax + By = gcd(A, B) の整数解 x , y を求めてください。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    // ax + by = gcd(a,b) の答えを x , y に代入する
    static long Extgcd(long a, long b, ref long x, ref long y)
    {
        long c = a;
        if (b != 0)
        {
            c = Extgcd(b, a % b, ref y, ref x);
            y -= (a / b) * x;
        }
        else
        {
            x = 1;
            y = 0;
        }
        return c;
    }

    static void Main()
    {
        int A, B;
        {
            int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            A = vs[0];
            B = vs[1];
        }
        long x = 0;
        long y = 0;
        Extgcd(A, B, ref x, ref y);
        Console.WriteLine($"{x} {y}");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

// ax + by = gcd(a,b) の答えを x , y に代入する

static long Extgcd(long a, long b, ref long x, ref long y)

{

long c = a;

if (b != 0)

{

c = Extgcd(b, a % b, ref y, ref x);

y -= (a / b) * x;

}

else

{

x = 1;

y = 0;

}

return c;

}

static void Main()

{

int A, B;

{

int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A = vs[0];

B = vs[1];

}

long x = 0;

long y = 0;

Extgcd(A, B, ref x, ref y);

Console.WriteLine($"{x} {y}");

}

意地悪すごろく (paizaランク C 相当)

意地悪すごろくのルールは次の通りです。

スタート地点のマス (0 マス目) から左右に無限にマスが続いていて、右が正のマス数、左が負のマス数となっており、N マス目にゴールマスがあります。

プレイヤーは -A , -B , 0 , 0 , A , B の 6 つの目を持つサイコロを振って出た目のマス数を移動します。
ただし、A , B は A ≠ B を満たす 1 以上 1,000 以下の自然数です。

N , A の値が与えられるので、1 ～ 1000 のうち、B として選ぶことで絶対にゴールできなくなる値を小さい方から順に全て出力してください。そのような値が存在しない場合は、-1 を出力してください。

入力されるデータ
N A

（ただし、1 ≦ N ≦ 100,000, 1 ≦ A ≦ 1,000）

N, A, B が与えられるとき、ゴールにたどりつけることは Ax + By = N の整数解 x, y が存在することを意味しています。

拡張ユークリッドの互除法では一次方程式 Ax + By = gcd(A, B) の整数解 x , y を求めましたが、これは方程式 Ax + By = C において C が gcd(A, B) であれば解が存在することを意味しています。また C が gcd(A, B) の整数倍であってもやはり解は存在します（A, B は C が gcd(A, B) のときの整数倍となる）。

なので、N が gcd(A, B) の整数倍ではない場合、N が gcd(A, B) では割り切れない B の値を探せばよいことになります。また問題文よりA ≠ B のときは除外します。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    // 最大公約数
    static long GCD(long a, long b)
    {
        while (a != 0 && b != 0)
        {
            if (a < b)
                b = b % a;
            else
                a = a % b;
        }
        return Math.Max(a, b);
    }

    static void Main()
    {
        int N, A;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            N = vs[0];
            A = vs[1];
        }

        bool find = false;
        for (int i = 1; i <= 1000; i++)
        {
            long gcd = GCD(A, i);
            if (N % gcd != 0 && i != A)
            {
                Console.WriteLine(i);
                find = true;
            }
        }
        if(!find) // ひとつも見つからない場合は -1 を出力する
            Console.WriteLine(-1);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

// 最大公約数

static long GCD(long a, long b)

{

while (a != 0 && b != 0)

{

if (a < b)

b = b % a;

else

a = a % b;

}

return Math.Max(a, b);

}

static void Main()

{

int N, A;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

N = vs[0];

A = vs[1];

}

bool find = false;

for (int i = 1; i <= 1000; i++)

{

long gcd = GCD(A, i);

if (N % gcd != 0 && i != A)

{

Console.WriteLine(i);

find = true;

}

if(!find) // ひとつも見つからない場合は -1 を出力する

Console.WriteLine(-1);

}

数学的な問題線分上の格子点の個数ユークリッドの互除法蟻本読書会

線分上の格子点の個数

最大公約数と最小公倍数

応用問題

拡張ユークリッド互除法

関連記事

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ