倍数の和による整数の表現
石畑 清（明治大学理工学部）
ishihata@cs.meiji.ac.jp

プログラミングコンテストでは，やさしい問題から難しい問題まで，さまざまな難易度の問題を取り揃え法を比較検討するプロムナードの題材としてピッタリだと考えた．て出題する．これは，参加チームのプログラミング能力に大きな差があることに対する対策である．弱いチームにも 1 問は解いてもらいたい（1 問も解けずに落胆させることは避けたい）し，逆に強いチームにも手ごたえを感じてもらいたいと考えると，難易度にバラエティを持たせることは必然だと思われる．

■問題：倍数の和で表現できない整数の個数
3 つの整数 n, a, b が与えられている．いずれも，1以上 100 万以下である．1 以上 n 以下の整数のうち，審判から見ると，難易度に変化をつけることによっaibj の形で表せないものの個数（これを Unableて，チームの強弱の差がはっきりするという利点があCount と呼ぶことにする）を求めよ．ここで，i も j もる．やさしい問題ばかりだと皆解けてしまうし，難し0 以上の整数とする．

い問題ばかりだと誰も解けないという結果になる可能性が大きい．このいずれの場合でも，成績に有意な差

たとえば，a2, b5 だったとする．1 〜 10 の範囲の整数の表現法を調べてみると，次のようになる．

は認めにくくなる．難易度に変化があれば，どの問題まで解けたかで，強弱の差がはっきり現れるだろう．

22150

逆に，参加チームから見た場合，どの問題がやさし42250

くて，どの問題が難しいかを見分けることがまず重要

52051になる．そして，やさしい問題を手早く片付けること

62350に努めるべきである．勝敗の分かれ目は，難しい問題

72151を解けるかどうかにあることが多いが，同じ問題数の82450

場合は，問題を解くまでの時間の短い方が勝ちだから

92251である．

1025502052

この連載では，今まで難しい問題をいかに解くかと.....

いうことに重点を置いてきた．プログラムの書き方に関する解説なのだから，これは当然である．誰にでも5 以上の数がすべて 2i5j の形で表せることは解けるような問題では，解説する甲斐がない．しかし，すぐに分かるだろう．奇数かつ 5 以上なら 2i51

やさしい問題の中にも議論すべきテーマを含んでいると書けるし，偶数なら 2i50 と書けるからである．

ものがある．今回は，そのようなやさしい問題の 1 つ結論として，この形で表せない正の数は 1 と 3 の 2を取り上げることにした．1999 年の国内予選問題 Bつだけである．n3 ならば，この問題の答は 2 とす「Unable Count」である．

ればよい．n1 または 2 なら，1 が答である．

この問題は，どうやっても解けるといえるほどやさ

a と b の最大公約数を gcd(a, b) と書くことにするしいのだが，問題を解くに至る道筋が一通りでない．と，aibj は必ず gcd(a, b) の倍数になる．つまり，さまざまな方向からのアプローチが可能で，解法のバgcd(a, b) の倍数以外の数は，初めから表せないことラエティが豊かである．いろいろなプログラミング技が分かっている．プログラムの中で，この事実を利用

84

44巻1号

情報処理

2003年1月

するかどうかは自由だが，いちおう頭の隅にとどめて切れれば，v が aibj の形で表せることが分かる

おくとよい．

ので，v に関する処理を打ち切って，次の数の処理に以下のプログラムでは，変数 n, a, b に 3 つの値が移る．プログラムでは，変数 x の初期値を v として，入力済みだと仮定する．さらに，a と b は交換してもこれから b を繰り返し引くことによって，vbj を結果が変わらないはずなので，ab になるよう，次得るようにしている．のような前処理を加えておくことにする．
if (a > b) {int tmp = a;a = b;b = tmp;}ab であることを利用すると，ある種のプログラ

こんな簡単な方法でよければ何の苦労もないのだが，そうは問屋がおろさない．この方法の計算量はO(n2) になる．内側の while 文の繰り返しは，最悪の場合 v/b 回程度である．これを 1vn の範囲で繰り返すから，全体の計算量は n の二乗を b で割ったものに比例する．具体的に計算時間が最もかかるデータとしては，n10 , ab2 の組合せがある．このデー6ムの計算時間を短くできることがある．

タに対して，上のようなプログラムを走らせたとこ

Unable Count を求めるプログラムは，ろ，筆者の計算機で結果が出るまでに 7 時間ほどかかった．

int unable_count(void);

インターネット経由で開催される予選の問題なので，プログラムの実行時間に制限はない（大会の場合で定義される関数 unable_count の形に書くことには 3 分を上限とすることが普通）．しかし，競技開始する．この関数の返り値が求める Unable Count の値から終了まで 3 時間半しかないのだから，7 時間もかである．

かるプログラムでは，答が出る前にコンテストが終わってしまう．失格間違いなしである．

2■ O(n ) の単純な解法

ところが，審判団はこのような単純なプログラムが多く提出されるとは予想していなかった．このプログ

最初に，参加チームが提出したプログラムのほとん

ラムが苦手とする上記のようなデータを用意していなどに採用されていた単純明快な方法を示す．1 〜 n のかったので，単純なプログラムでも合格になってしま数それぞれについて，aibj の形で表せるかどうった．

か調べるという方法である．
この方法によるプログラムの例を示す．
int unable_count(void){
int v, x, count;
count = n;
for (v = 1; v <= n; v++) {x = v;
while (x >= 0) {if (x%a == 0) {count--;
break;}
x -= b;}}return (count);}

調べる対象の数を v としている．j を増やしながら，これは審判団の一員として残念なことだったと考えている．確かに，ab2 のような（問題の本質から考えればおかしな）データを用意しようとは普通なら考えないだろう．しかし，審判の重要な仕事の 1 つは，どの程度遅いプログラムまで許すか決めることである．そして，その限度以上に遅いプログラムでは時間がかかりすぎて失格になるようなデータを用意しなければならない．この問題は，やさしい部類に属するので，このような配慮が必要だとは考えていなかったが，結果として手抜かりだった．

■ Hamming の問題
出題者は，Hamming の問題に対する有名な解法を流用すれば，Unable Count の問題も解けると考えていた．ちょっと横道にそれるが，この問題とその解法を紹介しておこう．

vbj が a で割り切れるかどうか順次調べる．割りIPSJ Magazine Vol.44 No.1 Jan. 2003

85

Hamming の問題とは，次のようなものである．
ijk• 2 3 5 の形の正の整数を小さい方から順に 700個生成せよ．

このプログラムは，マージの手法を応用している．
それまでに生成された数それぞれを 2 倍，3 倍，5 倍した 3 本の列があると想定して，これらをマージす
ijkる．生成済みの数は 2 3 5 の形で表せるものばか

別の言い方をすると，2, 3, 5 以外の素因数を持たなりなので，それを 2 倍，3 倍，5 倍したものも同じ形い整数の生成である．最初のいくつかを示すと，1, 2,で表せることは間違いない．また，この 3 種類で生成

3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32,すべき数すべてを尽くしていることもすぐに分かる．

36, 40, ... となる．

実際には，3 本の列を別に用意する必要はなく，元ijk

最初のうちは，2 3 5 の形で表せる数の密度がの列の各要素を 2 倍，3 倍，5 倍したものを仮想的な高いが，しだいにまばらになる．たとえば，696 番目列と考えればよい．マージは，それぞれの列の中に現の数 5668704 と 697 番目の数 5760000 の間には，こ在位置（2 倍の列が p, 3 倍の列が q, 5 倍の列が r）をの形で表せない数が 91295 個もある．1 から順に整数

設け，現在位置にある数の中で最も小さいものを出力を生成し，それぞれがこの形で表せるかどうか調べるに移すという標準的な方法を採っている．という単純な方法では，計算時間がかかりすぎる．2,3, 5 以外の素因数を持たない整数だけを無駄なく生成する方法が必要とされる．

■ Hamming の方法の応用による解法

この問題には効率的な解法が存在する．他の問題

Unable Count の 問 題 が Hamming の 問 題 と 同 じにはあまり現れない変わった形のプログラムになるの構 造 を し て い る こ と は 容 易 に 理 解 で き る と 思 う．

で，非常に印象的で一度聞いたら忘れられない．しかHamming の問題のべき乗を掛け算に変え，掛け算をし，文献に取り上げられることがあまり多くなかった

足し算に変えると Unable Count の問題になる．一方ようで，知る人ぞ知るの状態になっているのは不思議

は表せる数の列挙，もう一方は表せない数の個数のなことである．

計算という違いはあるが，この違いは重要なものでこの解法を C の関数として書くと，次のようになる．

はない．当然，Hamming の問題の解法を流用して，Unable Count の問題を解くことが可能である．

void hamming(int t[700]){
int p, q, r, s, x;
p = 0;
q = 0;
r = 0;
t[0] = 1;
s = 1;
while (s < 700) {x = 2*t[p];if (3*t[q] < x)
x = 3*t[q];if (5*t[r] < x)x = 5*t[r];t[s] = x;s++;if (x == 2*t[p])p++;if (x == 3*t[q])q++;if (x == 5*t[r])r++;}プログラムは次のようなものになるだろう．
int unable_count(void){
int p, q, s, x;
int t[1000001];
p = 0;
q = 0;
t[0] = 0;s = 1;for (;;) {if (t[p]+a <= t[q]+b)
x = t[p]+a;else
x = t[q]+b;if (x > n)break;
t[s] = x;s++;if (x == t[p]+a)p++;
if (x == t[q]+b)
q++;}
return (n-s+1);

}
}

86

44巻1号

情報処理

2003年1月

Hamming の 問 題 の 場 合 と 同 じ く，t[...]+a と0

a2a3a4a.....

t[...]+b が 2 本の仮想的な列に当たる．この 2 本

bb+ab+2ab+3ab+4a.....の列をマージして，aibj の形で表現できる数を2b2b+a2b+2a2b+3a2b+4a.....

順次生成していく．添字 p と q がそれぞれの列の現3b3b+a3b+2a3b+3a3b+4a.....

在位置である．生成できた数は，配列 t に順に入れ.......

る．最終的な結果は n から生成できた数の個数（s1,(a-1)b (a-1)b+a (a-1)b+2a (a-1)b+3a (a-1)b+4a .....

1 を引くのは 0 が勘定に入らないから）を引いたものである．

横方向の繰り返しは，n に達するまで続ける．一方，この方法の計算量は O(n) である．while 文の繰り返

縦方向の繰り返しは bj について 0ja1 の範囲だ

しは，最悪の場合でも n1 回にしかならない．while

けでよい．たとえば，ja の列を考えると，先頭の要文の中には繰り返しが含まれていないので，O(n) で素は ab だが，これは最初の列（0 が先頭）の要素と確実に終わる．

してマーク済みだからである．

この方法を改良した解法も考えられる．たとえば，連続した a 個の整数（gcd(a, b) の倍数の a 個の連続）

たとえば，a3, b4 の場合のマークの付け方は次のようになる．

が生成できれば，そこから先すべての整数が生成できることは間違いない．この判定条件を加えれば，0369121518...

while 文の実行回数を少なくすることができるだろ

471013161922...

う．しかし，これはプログラムを複雑にするばかりで，8111417202326...

実行時間の得は大きくない．ここでは，これ以上詳しく調べることはしない．
後から反省してみると，Unable Count の問題の解法として，ここに示したような難しいものを想定した の は， 少 し 考 え す ぎ で あ っ た．Unable Count は，Hamming の問題よりずっとやさしいので，これほど高級な考え方を採用する必要はないのである．もっと単純で，しかも同じくらい速い解法を次に示す．

1, 2, 5 の 3 つがマークされずに残るので，UnableCount の値は 3 だと分かる（n5 であれば）．
この方法によるプログラムの例は次のとおりである．
int unable_count(void){
int i, j, x, count;
int table[1000001];
for (i = 0; i <= n; i++)table[i] = 0;
for (j = 0; j < a; j++) {x = b*j;if (x > n)break;
while (x <= n) {table[x] = 1;
x += a;}}count = 0;
for (i = 1; i <= n; i++)if (table[i] == 0)
count++;
return (count);■マーク付けによる解法
Unable Count の 問 題 は， 素 数 の 表 を 作 る た め の「Eratosthenes のふるい」と同じような考え方でも解ける．数 1 つにつき 1 ビットのメモリを用意する．そして，aibj の形で表現できる数それぞれにマーク（印）を付けていく．該当する数すべてにマークを付け終わってから，1 〜 n の範囲でマークの付いていない数の個数を数えればよい．
これは，非常に素直な考え方で，プログラミングも簡単である．しかも，この方法でも O(n) の計算量が得られる．Hamming の解法の応用が大げさだと言っ}たのは，このような事情があるからである．
マークは，次のような順番で付けていく．

プログラムの中ほどにある 2 行，
if (x > n)break;IPSJ Magazine Vol.44 No.1 Jan. 2003

87

は，論理的には不要である．x が n より大きいなら，明できる．

次の while 文を 1 回も実行しないことになるので，無1 つの数に 1 回しかマークしないと聞いて，性能が理に途中で脱出しなくても，結果は同じになるはずでよくなると安心してはならない．これではマークの存ある．しかし，現実にはオーバーフローという問題が在価値がなくなるのである．そもそも，マークが役にある．j が大きくなると，b*j がオーバーフローする

立つのは，1 つの数が 2 カ所以上に現れ得る場合であ可能性が生じる．こうなると結果がどうなるか分からる．1 つの数に何回マークしようとも，最後に数えるなくなる．そうなる前，b*j が n より大きくなった

ときは 1 つにしかならないということがマーク付け

時点で繰り返しを打ち切ってしまえば，このような問の方法のポイントである．そのポイントが効果を発揮題を避けられる．

しないような状況なら，マーク付けの方法の意義その

この方法の計算量は O(n) である．上に示した図のものを疑わなければならない．

横 1 列のマークに O(n/a) の計算量がかかる．これをj の範囲を 0ja/gcd(a, b)1 に限定すると，あるa 回繰り返せばよいのだから，O(n/a)a で O(n) とな数にマークしようとしたときに，その数にすでにマーる．

クが付いていることはない．それなら，それぞれの系

このような簡単なプログラムで，十分な速度を持つ列で何個マークするかを計算して，それを加えるだけプログラムが書けることが分かったので，出題者の意

でマークの総数が求まる．
系列ごとのマークの個数は，図は大きくくじかれたが，実はこれで終わりではなか割算で簡単に計算できる．マークのための配列をことった．さらに簡単で，しかも速いプログラムが可能でさら用意する必要などない．

ある．この方法について次に述べる．

この考え方でプログラムを書くと次のようになる．
int unable_count(void){
int g, j, count;■マーク付けの方法の改良
前ページのプログラムでは，縦方向の繰り返しの範g = gcd(a, b);count = n+1;
for (j = 0; j < a/g; j++) {if (b*j > n)break;count -= (n-b*j)/a+1;}
return (count);

囲を 0ja1 としているが，これには無駄がある．

gcd(a, b) が 1 で な い な ら ば，0ja/gcd(a, b)1 の範囲で十分である．
たとえば，a6, b10 のケースでは，

061218243036...

1016 2228344046...

2026 3238445056...

}

変数 count の初期値が n1 になっているのは，0もマークの対象になっているからである．これを勘定の 3 列だけマークすればよい．次の 30 から始まる系からはずすために 1 を加えている．

列は，0 から始まる系列でマーク済みだから，改めてこのプログラムの繰り返しの回数は a/gcd(a, b) とマークしなくてよい．この場合，a6, b10 だから，n/b のどちらか小さい方である．bj が n を超えたら，gcd(a, b)2 である．j の範囲は，0ja/gcd(a, b)1

そこで打ち切って差し支えないからである．最悪のケ6212 とした．

ースとして，gcd(a, b)1 の場合を考えると，a と n/b

この考え方をプログラムに取り入れるのは簡単であのどちらか小さい方ということになる．最初に述べた

る．1 つ前のプログラムの for 文の上限の式を変える

とおり，一般性を失うことなく ab としてかまわなだけである．改めてプログラムを示すことは控えよう．

いので，この値が最大になるのは ab √n の場合でマークの出発点となる bj の j の範囲をこのようにあり，その場合の値は√n であることが分かる．した

限定すると，同じ数が表の中の 2 カ所以上に現れるがって，このプログラムの計算量は O( √n) である．

ことはなくなる．数学的な用語でいうと，aibj

最 大 公 約 数 gcd(a, b) を 求 め る 部 分 の 計 算 量 は，apbq, 0j, qa/gcd(a, b)1 に な る と す れ ば，Euclid の互除法を使えば O(log n) になるので，O( √n)ip, jq の場合しかあり得ない．このことは簡単に証より小さく，全体の計算量には影響しない．

8844巻1号

情報処理

2003年1月

■数学の問題かプログラミングの問題かかし，これは言うは易く，行うは難しであって，なかなか思うようにはいかない．また，ここまでが数学で，最後の方法の計算量は，O( √n) である．出題者のここからがプログラミングとはっきり切れるものでは想定していた方法より，だいぶ速くすることができた．

ないし，数学的な分析を要するプログラミング問題がしかし，この方法でやっている仕事の内容は，実につ必ず悪いというものでもない．ほどほどにというしかまらないものだといわざるを得ない．割算の答をいくないのかもしれない．

つか加え合わせているだけである．プログラミングとしては，まったく面白味のないものになってしまった．

なお，Unable Count の問題に戻って，a と b が互いに素であって，かつ n が十分大きければ，結局，この問題のポイントは数学にあったことが分かる．最後の解が目標だとすれば，そこに至るまでの(a1)(b1)/2数学的な考察を行えるかどうかが鍵であり，プログラミングの能力は重要でない．これはプログラミングコという閉じた式で表せることが分かっている．n が十ンテストの問題として望ましいことではない．Unable

分大きいとは，曖昧な言い方だが，たとえば ab よCount は，コンテスト問題として失敗作だったというり大きければ，十分大きいといってよい．

評価があり得る．

2 つの条件のうち，互いに素の方は，成立していな

一方で，学生がすぐに最後の方法に到達できるはずくても対処できる．a と b が互いに素でない場合は，もなく，途中でいろいろな方法の得失を体験するはず

最大公約数で割ってから同じような計算をすればよだと考えれば，教育的に見て非常によい問題だったとい．しかし，もう一方は簡単に対処できそうもない．

いう評価もあり得るだろう．実際，筆者は，ここまでn が小さい場合にまで適用できる一般的な式があるかに示したような考察を大いに楽しんだ．

どうかは不明である．n が小さい場合は，今までに示この問題をどう評価するかは見解の分かれるところだと思う．

した方法のどれかを使うようなプログラムを書くしかなかろう．

プログラミングコンテストの問題を作る過程で，数n が小さい場合は別としても，最大公約数の計算に学に力点があるか，プログラミングに力点があるかとO(log n) の計算量がかかるので，閉じた式とはいっていうことをよく議論する．
数学の部分だけが難しくて，も，最後に示した方法に比べて格段に優れているとまそこを突破すれば簡単なプログラミングだけという問ではいえないようである．

題はなるべく避けたいと多くの審判が思っている．し（平成 14 年 12 月 2 日受付）

IPSJ Magazine Vol.44 No.1 Jan. 2003

89