約数、因数分解、累乗数、GCD、LCMに関する知見

・約数

整数Nの約数の列挙はO(N^(1/2))でできる。

例えば10であれば1から10^(1/2)までの1,2,3を調べれば良い。
割り切れれば割った値と割られた値が約数である。
10の約数は1,2,5,10の4つ。

注意として例えば36のとき、
1,2,3,4,6,6,9,12,18,36の10つではなく、
1,2,3,4,6,9,12,18,36の9つが答えであること。

それ以下の数のうち約数のもっとも多い数を高度合成数という。
1000000000以下の最大の高度合成数は735134400。
735134400 = 2^6*3^3*5^2*7*11*13*17
その場合の約数は1344個。

1000以下だと840で32個。
10000以下だと7560で64個。
100000以下だと83160で128個。

・素数

ある数の素数の判定はO(N^(1/2))でできる。
判定方法は約数が2つしかないかどうかを調べるので、
結局は約数の列挙と同じ方法になる。
ミラーラビン素数判定法を使えばもっと高速であるが、
使うような問題が出ることは無いように思う。

1からNまでのすべての素数判定を行う場合、
エラトステネスの篩を使うとO(NloglogN)で求めることができる。

素数の数は意外に多い。
感覚的には10個に1個は素数くらいの感覚で良いと思う。

素数の数。

10000までは1229個。
100000までは9592個。
1000000までは78498個。
10000000までは664579個。
100000000までは5761455個。
1000000000までは50847534個。

・累乗数

a^x*a^y=a^(x+y)
a^x/a^y=a^x*a^(-y)=a^(x-y)
a^x*b^y=(a^(x/gcd(x,y))*b^(y/gcd(x,y)))^gcd(x,y)

・因数

整数Nの因数の列挙も因数分解もO(N^(1/2))でできる。

整数NをO(N^(1/2))で因数分解する場合、
小さい値の2からN^(1/2)まで順に割れるだけ割っていく。
最後に残った値は1で無ければ追加する。

因数分解はO(NloglogN)の前準備をしておくと、
それ以降は全ての1からNをO(logN)で因数分解できる方法がある。

まず前準備として素数であれば0、素数で無ければ最小の因数である表を準備する。
これはエラトステネスの篩と同じようなやり方でできる。
次に、Nを素因数分解するときに表を見ながら素数でなければ、
表にある最小の因数を結果に追加しつつ割り切れるまで割っていく、
最後に素数が残ったらそれも結果に追加する。
この方法はO(logN)である。

因数がいちばん多いのは因数が2のみの場合。
1000000000以下でもっとも因数の数が多いのは536870912で29個。
1000000000以下でもっとも因数の種類が多いのは223092870で9個。
2*3*5*7*11*13*17*19*23=223092870。

なお、因数分解ができているのであれば約数の数も計算できる。
約数の数は指数に1を加算してすべて掛け算したものになる。
例えば、2^1*3^3であれば約数の数は(1+1)*(3+1)個である。

・最大公約数

最大公約数はgcdを使っていく。

gcd(a,b,c) = gcd(a,gcd(b,c))である。

64ビット整数値におさまらないときがある。
よって因数と指数の数を次のように覚えていく方法がある。
指数の小さいほうを使う。

2^3*5*11と2^2*5*7を結合すると2^2*5となる。

・最小公倍数

最小公倍数の結合はlcmを使ってやれば良い。

lcm(a,b,c) = lcm(a,lcm(b,c))である。

64ビット整数値におさまらないときがある。
よって因数と指数の数を次のように覚えていく方法がある。
指数の大きいほうを使う。

2^3*5*11と2^2*5^2*7を結合すると2^3*5^2*7*11となる。

・最大公約数と最小公倍数

以下のような式が成り立つ

gcd(a,b)*lcm(a,b)=a*b

a,bがわかっていればgcdとlcmの入れ替えは意外に簡単。

・拡張ユークリッド互除法

拡張ユークリッドの互除法を使うと以下の整数解(x,y)を計算できる。

ax+by = gcd(a,b)

ax+by=a(x+b)+b(y-a)であることから複数の(x,y)が求まる。

特にgcd(a,b)=1のときに、

ax+by=cであれば整数解は(cx,cy)となる。

問題１：

a^b <= N となるような整数a,bは何通りか？1<=a,b,N<=10^9。

例えば、N=2のとき(a,b)=(1,1),(1,2),(2,1)の3通りある。

このような累乗の問題は1を別に考えると良い場合が多い。

例えば、a=1のときすべてのbは有効なのでN通りであることがわかる。
また、b=1のときもaが1からNまで有効でN通りあることがわかる。
この2つの場合で1^1が共通するので1が存在する場合は(N+N-1)通りとわかる。

さて、1の場合を数え終えたのであとはa,b>=2の場合だけを考えれば良いです。
a=1のときにN通りも答えが存在するのでa=2のときにもたくさんありそうですが、
実際にN=10^9、a=2のときbはたったの29通りしかありません。
1より大きい整数は2以上の累乗で爆発的に増えると覚えておくと良い。
よって、a>=2のときbは30程度まで調べておけばいい。

では、aは2からいくつまで調べれば良いかというと、
b>=2なので(10^9)^(1/2)を超える程度までやれば良い。
よって、aは2から32000くらいまで調べれば良い。

結局、N=10^9のときでもa,b>=2なら30*32000程度のループで全探索できる。

問題２：

N個の数Aiがあります。1<=N<=50。1<=Ai<=10。
ここから1個以上の数をいくつか取り出して全て掛け算します。
この結果が数Kで割り切れる場合は何通りあるでしょう？1<=K<=10^9。

例えば、N=3、Ai={2,2,8}、K=16のとき、
答えは{2,8}、{2,8}、{2,2,8}の3通りあります。

この問題の場合、全ての掛け算をしてしまうと、
例えば8が50個のときなどに64ビット整数値でオーバーフローしてしまいます。
よって、実際に掛け算せずに因数が何個あるかを覚えていくようにします。
このようにすれば8が50個のときも因数2が150個まで覚えれば良いです。
Aiの範囲が1から10までであるから因数は2,3,5,7しかありません。
よって、配列d[151][101][51][51]に記録するような方法があります。
また、Kは最大10^9までなので、実はd[31][20][14][12]まで覚えておけば良い。
Kの因数を調べて全ての因数の指数が以上であれば答えに含みます。

問題３：

gcd(a,b)=X、lcm(a,b)=Yとなるような正の整数X,Yがある。1<=X,Y<=10^9。
この条件を満たすa,bのうちa+bが最小になるものを答えよ。
ただし、そのようなものが無い場合は-1を答えとする。

例えば、X=6,Y=36のとき、a+b=6+36か12+18であり最小は30になります。

まず簡単な例として、X=2*3、Y=2^2*3^2と考えます。
gcd(a,b)はa,bの因数の各指数の小さいものをとったもの、
lcm(a,b)はa,bの因数の各指数の大きいものをとったもの、
と考えますので、
XからYの増分2*3がもともとa,bのどちらのものかを考えれば良いです。
すなわち、次の4通りが考えられます。
a=2*3、b=2^2*3^2
a=2^2*3,b=2*3^2
a=2*3^2,b=2^2*3
a=2^2*3^2,b=2*3
結局、2*3=Y/Xの約数を求めて、
約数と約数で割った値をa,bに振り分けて全探索できます。
ちなみにYがXで割り切れない場合は答えが-1となります。