中国剰余定理について

中国剰余定理についての話です。
きっかけは、paizaラーニングのレベルアップ問題集「素数メニュー」からの出題でした。
paiza.jp

中国剰余定理とは、Wikipediaによれば...
>中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。
>あるいは、それを一般化した可換環論における定理でもある。
>中国人の剰余定理、孫子の定理とも呼ばれる。
ja.wikipedia.org
>3～5世紀頃成立したといわれている中国の算術書『孫子算経』には、以下のような問題とその解答が書かれている。
>今有物、不知其数。三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。問物幾何？
>答曰：二十三。
>術曰：『三・三数之、剰二』、置一百四十。『五・五数之、剰三』、置六十三。『七・七数之、剰二』、置三十。并之、得二百三十三。以二百一十減之、即得。凡、三・三数之、剰一、則置七十。五・五数之、剰一、則置二十一。七・七数之、剰一、則置十五。一百六以上、以一百五減之、即得。

>日本語では、以下のようになる。
>今物が有るが、その数はわからない。三つずつにして物を数えると、二余る。五で割ると、三余る。七で割ると、二余る。物はいくつあるか？
>答え：二十三。
>解法：三で割ると、二余る数として、百四十と置く。五で割ると、三余る数として、六十三と置く。七で割ると、二余る数として、三十と置く。これらを足し合わせて、二百三十三を得る。これから二百十を引いて、答えを得る。一般に、三つずつにして物を数え、一余ると、その度に七十と置く。五で割った余りに二十一をかける。七で割った余りに十五をかける。百六以上ならば、百五を引くことで、答えを得る。

>この問題は、『孫子算経』とともに日本にも伝わり、後に和算の隆盛した江戸時代には、「百五減算」として知られた。

なんか「なぞなぞ」っぽいけれども、要するに「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法です。

そして、paizaラーニングのレベルアップ問題集「素数メニュー」の出題では...
「m1 と m2 を互いに素な正の整数とする。Z を m1 で割った余りが b1 であり、Z を m2 で割ったあまりが b2 であるような整数 Z が 0 以上 m1 × m2 未満にただ 1 つ存在する」
として、「上記の定理の m1 , m2 , b1 , b2 の値が与えられるので、これらに対応する 0 以上 m1 × m2 未満の整数 Z を求めてください」という出題でした。
なるほど、もう解けましたー。

僕が作成、提出したコードは、以下のとおりです。

・中国剰余定理

/*
C++による「素数メニュー」問題集
中国剰余定理
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll m1,m2,b1,b2;
    cin>>m1>>m2>>b1>>b2;
    for(ll i=0;i<m2;i++){
        ll z=m1*i+b1;
        if(z%m2==b2){
            cout<<z<<endl;
            return 0;
        }
    }
}

中国剰余定理によって、m1 , m2 , b1 , b2 に対応する整数 Z が 0 以上 m1 × m2 未満に必ず 1 つ存在することが保証されています。

補助定理としては...
>与えられた二つの整数 m, n が互いに素ならば、任意に与えられる整数 a, b に対し、連立合同方程式
>x ≡ a (mod m),
>x ≡ b (mod n)
>を満たす整数 x が mn を法として一意的に存在する。

一般的な定理については...
>与えられた k 個の整数 m1, m2, ..., mk がどの二つも互いに素ならば、任意に与えられる整数 a1, a2, ..., ak に対し
>x ≡ a1 (mod m1),
>x ≡ a2 (mod m2),
>　　　…
>x ≡ ak (mod mk)
>を満たす整数 x が m1m2…mk を法として一意的に存在する。

で、『孫子算経』については、初めて知りました。
Wikipediaによれば...
ja.wikipedia.org
>南北朝時代に書かれた算術書であり、孫子算経は3巻から成っている。
・上巻では、度量衡の単位と、算木の使い方（籌算）について詳しく論じられている。算木は春秋時代から使われ、算数書（中国語版）や九章算術にも現れてはいるが、算木を使った詳しい算法についてはそれらに残っていない。孫子算経では、「算木の置き方は、一は縦、十は横、百は立ち、千は倒れる」という置き方や、さらには四則演算をどのように進めていくかも、充分な具体例と共に記されている。
・中巻では、算木で分数を扱っている。計算として加減乗除に加えて、開平法についても扱っている。
・下巻では、問28でのちに中国剰余定理と呼ばれる算法について扱われているほか、問31にキジとウサギを数える「雉兎同籠」（日本では鶴亀算となった）がある。

あっ、下巻にあるみたいです、中国剰余定理。
国立国会図書館デジタルコレクションで公開されてました。
dl.ndl.go.jp

paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。