SRM613 Div1 Medium "RandomGCD"
問題
TopCoder Statistics - Problem Statement
訳
lowからhighまでの整数を考える。この範囲からN個の整数を使ってシーケンスを作る。このシーケンスは値の重複が許される。よってシーケンスは(high - low + 1) ^ Nだけ作れることになる。
それらのシーケンスの内、最大公約数がKであるようなシーケンスだけを選び出したい。
あなたはint N, K, low, highが与えられる。上記のシーケンスを数え上げよ。
制約
1 <= N, K <= 10^9
low <= high <= 10^9
0 <= high - low <= 10^5
cgy4everさんのコードを見て
まず最大公約数をKにしなければならないので、low~highの中でKで割り切れないものは考えなくてもよい。low~highでKで割り切れるものを抜き出してみる。
low = 11, high = 24, K = 2とすると、 {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24} ↓ {12, 14, 16, 18, 20, 22, 24}
これらをKで割る。そうすると、Kを何倍したものがlow~highの中にあるのかが出てくる
{12, 14, 16, 18, 20, 22, 24} ↓ {6, 7, 8, 9, 10, 11, 12}
ここから最大公倍数が1になるようにシーケンスを作っていけばいいことになる。
6と7 つまり12と14 -> OK 6と8 つまり12と16 -> 最大公約数が4になるのでNG
最大公約数が1の組み合わせの数え上げの方法は次のようにやる。まず公約数が1のものを数え上げる。そこから公約数が2のものを引く。さらに公約数が3のものを引く。さらに公約数が4のものを引く。さらに公約数が5のものを引く。さらに公約数が6のものを引く。..といった具合にできる。
当然問題がある。それは、引きすぎていることである。公約数が2のものを引いて、3のものを引けば、6のものはもう引き終わってんじゃないの?つーか6は2回引いてるんだから逆に1回足さなきゃいけないんじゃないの?ということになってしまう。
そこで、「公約数iはどのくらい足すの引くのボックス」を作ることにする。
まずボックスの初期値は全て0にしておく
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ | |
どのくらい足すの引くの | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ・・・ |
公約数1のターン
題意より、公約数1のものは1回足したいので、1とする。
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ | |
どのくらい足すの引くの | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ・・・ |
そうすることにより、1で割り切れる公約数も当然足されてしまうため公約数2~を+1とする
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ | |
どのくらい足すの引くの | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ・・・ |
公約数2のターン
題意より、公約数2は数え上げはしたくないのでトータルで0にしないといけない。公約数1を1回数え上げたことによって、公約数2も1回数え上げられてしまっているので、1回引かなくてはならない。よって、公約数2を-1とする。
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ・・・ |
公約数2を-1回数え上げる(1回引く)ことにより、2で割り切れる公約数も-1回数え上げることになるため、4, 6, 8, 10~から1引く
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | ・・・ |
公約数3のターン
題意より、公約数3は数え上げはしたくないのでトータルで0にしないといけない。公約数1を1回数え上げたことによって、公約数3も1回数え上げられてしまっているので、1回引かなくてはならない。よって、公約数3を-1とする。
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | -1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | ・・・ |
公約数3を-1回数え上げる(1回引く)ことにより、3で割り切れる公約数も-1回数え上げることになるため、6, 9, 12~から1引く
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | -1 | 0 | 1 | -1 | 1 | 0 | 0 | 0 | 1 | -1 | 1 | ・・・ |
公約数4のターン
題意より、公約数4は数え上げはしたくないのでトータルで0にしないといけないが、どうも既になっているようだ。よって何もしなくてよい。
公約数5のターン
題意より(ry
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | -1 | 0 | -1 | -1 | 1 | 0 | 0 | 0 | 1 | -1 | 1 | ・・・ |
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | -1 | 0 | -1 | -1 | 1 | 0 | 0 | -1 | 1 | -1 | 1 | ・・・ |
公約数6のターン
題意より(ry
な・・・なんとこれまでの足し引きの結果-1回数え上げられてしまっている。ここは数え上げ0回にするため、今までとは逆に1回数え上げなければならない。よって公約数6を1とする。
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | -1 | 0 | -1 | 1 | 1 | 0 | 0 | -1 | 1 | -1 | 1 | ・・・ |
公約数12, 18, 24~は1足されることとなる。
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | -1 | 0 | -1 | 1 | 1 | 0 | 0 | -1 | 1 | 0 | 1 | ・・・ |
そんなこんなで完成!
公約数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ・・・ |
どのくらい足すの引くの | 1 | -1 | -1 | 0 | -1 | 1 | -1 | 0 | 0 | 1 | -1 | 0 | -1 | ・・・ |
これで、公約数iの組み合わせはどれだけ足し引きすればよいのかが分かった。
この考え方は「包除原理」というものらしいです。
ボックスを作ったところで、さっそく公約数1,2,3...の組み合わせを数え上げていく。先ほどのKで割ったシーケンスを見てみる。ここで、最小のものをL,最大のものをRとする。
{6, 7, 8, 9, 10, 11, 12} ↓ L = 6, R = 12
公約数1から考えていく。L~Rまでの間に、1を約数としてもつものは何個あるかというと、7個である(全部当てはまるから)。なので、公約数1のシーケンスは7^Nだけ作れることになる。公約数1はどのくらい足すのかボックスを覗いてみると「+1」とのことなので、答えに7^Nを足してあげる。
次に公約数2を考える。L~Rまでの間に、2を約数としているものは4個。つまり作れるシーケンスは4^N個。ボックスを覗くと「-1」。よって答えから4^N個引いてあげる。
・・・というのを公約数Rまでやって、答えを足し引きしてあげればよい。
だがしかし、Rは最大で10^9にもなるため無理である。そこで、{5, 5, 5,..., 5}といった同じ要素の数列は考えないことにする。そもそもその数列は最小公倍数が1じゃないし(例外あり)、こうすることで、1~(R-L)までの公倍数だけを考えればよくなる。なぜなら(R-L+1)以上の倍数Xを持つ要素はL~Rの中に最大1つしか存在しないので、Xを公約数とした組み合わせを数え上げたり引いたりしていないからである({5, 5, 5,..., 5}とかは考えない事にしたので)。ただし、例外としてL = 1の場合のみ{1, 1, 1,..., 1}を数え上げなければならないので、答えに+1しておかなくてはならない。
ソースコード
int box[100001]; long long mod = 1000000007LL; class RandomGCD { public: long long pow(long long a, long long b) { long long r = 1; while (b > 0) { if (b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; } int countTuples(int N, int K, int low, int high) { // 公約数iはどのくらい足すの引くのボックス生成 memset(box, 0, sizeof(box)); for (int i = 1; i <= 100000; i++) { if (i == 1) { // 最大公約数1は1にしたい box[i] = 1; } else{ // 公約数1以外は0にしたい // mul[i]に今まで足された数が入っているので、 // その分を引くようにする box[i] *= -1; } for (int j = i + i; j <= 100000; j += i) { box[j] += box[i]; } } // L, R生成 int L = (low + K - 1) / K; int R = high / K; if (R < L) return 0; // Kが約数のものはない long long ans = 0; if (L == 1) ans++; // Lが1だったら{ 1, 1, 1,..., 1 }はOK for (int i = 1; i <= R - L; i++) { // v := L~Rの間にiを約数として持つものはいくつあるか long long v = R / i - (L - 1) / i; ans += pow(v, N) * box[i]; ans -= v * box[i]; // {5, 5, 5,..., 5}などは考えない ans += mod; ans %= mod; } return (int)ans; } };