yukicoder contest 368 B
解き方
※ ここに書く解き方は、解説に書かれている解き方と異なる $ P と$ Q は互いに素である場合のみ考えれば十分なため、以下では$ P と$ Q は互いに素とする。
（もし互いに素でない場合は、最大公約数でそれぞれを割れば良い）
ここで、正整数$ N と$ M が$ \frac{1}{N} + \frac{1}{M} = \frac{P}{Q} を満たすと仮定する。
また、$ d を$ N と$ M の最大公約数として、正整数$ N^{\prime} を$ N^{\prime} = \frac{N}{d} とする。同様に正整数$ M^{\prime} を$ M^{\prime} = \frac{M}{d} とする。
このとき$ \frac{1}{N} + \frac{1}{M} = \frac{N^{\prime}+M^{\prime}}{dN^{\prime}M^{\prime}} となるため、これが$ \frac{P}{Q} に等しいことと、$ P と$ Q が互いに素であることから、次のことがわかる。
正整数$ k が存在して、$ N^{\prime}+M^{\prime} = kP かつ$ dN^{\prime}M^{\prime} = kQを満たす。
よって、上の条件を満たす正整数を$ k とする。
定義より$ N^{\prime} と$ M^{\prime} は互いに素であるため、$ N^{\prime}+M^{\prime} と$ N^{\prime}M^{\prime} は互いに素である。
$ N^{\prime}+M^{\prime} = kP という条件から、$ k は$ N^{\prime}+M^{\prime} = kP の約数であるため、$ k と$ N^{\prime}M^{\prime} は互いに素である。
以上から$ d が$ k の倍数でことがわかるため、$ d^{\prime} = \frac{d}{k} とすることで、上の条件は次のように言い換えられる。
正整数$ N と$ M が$ \frac{1}{N} + \frac{1}{M} = \frac{P}{Q} を満たすならば、ある正整数$ N^{\prime} と$ M^{\prime} が存在し、次の4つの条件を満たす。
1. $ N^{\prime}+M^{\prime} が$ P の倍数である。すなわち、$ k = \frac{N^{\prime}+M^{\prime}}{P} は正整数である。
2. $ N^{\prime}M^{\prime} が$ Q の約数である。すなわち、$ d^{\prime} = \frac{Q}{N^{\prime}M^{\prime}} は正整数である。
3. $ N = kd^{\prime}N^{\prime} をみたす。
4. $ M = kd^{\prime}M^{\prime} をみたす。
これは正整数$ N と$ M が$ \frac{1}{N} + \frac{1}{M} = \frac{P}{Q} を満たすための必要条件である。
逆に、上の4つの条件のうち1 と2 を満たす正整数$ N^{\prime} と$ M^{\prime} が存在したときは、上の条件の3 と4 を満たすように$ N と$ M を定めることで、$ \frac{1}{N} + \frac{1}{M} = \frac{P}{Q} を満たすことができる。
以上から、上の4つの条件のうち1 と2 を満たす正整数$ N^{\prime} と$ M^{\prime} を全て列挙すれば、$ \frac{1}{N} + \frac{1}{M} = \frac{P}{Q} を満たす$ N と$ M の組を全て列挙することが可能である。
4つの条件のうち2 の条件に着目すると、$ N^{\prime} と$ M^{\prime} はいずれも$ Q の約数であるため、$ Q の約数を列挙し、全ての約数のペアについて、上の条件を確認すれば良い。
$ Q の約数の個数を$ D とすると、$ Q の約数の列挙は$ O(\sqrt{Q}) 、全ての約数のペアについて条件を確認するのは$ O(D^{2}) の計算量で可能であるが、重複の排除と出力のためにソートが必要である。
以上より、$ O(\sqrt{Q}+D^{2} \log D) の計算量でこの問題を解くことができる。アルゴ式の記事によると、$ 10^{9} 以下の数について、約数の個数は最大でも$ 1344 個であるため、上の計算量であれば実行時間制限内に実行可能と思われる。 （ただし、あまり余裕のある計算量とは言えないため、コンテスト終了後に以下の計算量削減の考察をした）
上の議論を思い返すと、$ Q の約数のペアを全て確認する必要はなく、互いに素であるような約数のペアだけ考えれば十分であることがわかる。
よって、$ Q の約数のペアのうち、互いに素であるようなものの個数を考えたいが、まずは簡単のために次のような場合を考える。（一般の場合は後述）
$ Q が互いに異なる$ n 個の素数の積であるとする。
すなわち、互いに異なる$ n 個の素数$ p_1, p_2, \ldots, p_n が存在し、$ Q = \prod_{i=1}^{n} p_i を満たすとする。
このとき、$ Q の約数の個数は$ D = 2^{n} となるが、約数のペアのうち互いに素であるようなものの個数は$ 3^{n} 個である。
これは、包含関係にある2つの部分集合のペアの個数が$ 3^{n} であることと同様に、下のように考えればわかる。
$ n 個の素因数それぞれについて、「$ N^{\prime} に含まれる」「$ M^{\prime} に含まれる」「どちらにも含まれない」の3通りの状態が考えられるため、全体で$ 3^{n} 個になる。
（今は$ N^{\prime} と$ M^{\prime} が互いに素である場合を考えているため、「どちらにも含まれる」という状態は考えない）
よって、このときは$ 3^{n} = D^{\log_{2} 3} より、$ Q の約数のペアのうち、互いに素であるようなものの個数は$ D^{\log_{2} 3} となる。
実は後述する通り、任意の正整数$ Q について、$ Q の約数のペアのうち、互いに素であるようなものの個数は$ D^{\log_{2} 3} 以下となることが示せる。
2つの約数が互いに素かを確認するには、事前に$ Q に含まれる素因数を列挙した上で、各bit で各素因数を含んでいるか否かを表すような数を、それぞれの約数に紐付けておけば良い。
素因数の列挙は$ O(\sqrt{Q}) の計算量で、約数に紐付ける数は$ O(D \log Q) の計算量で求められる。
$ \log_{2} 3 = \frac{\log_{10} 3}{\log_{10} 2} \lt 1.6 なので、全体の計算量は$ O(\sqrt{Q}+D \log Q + D^{1.6} \log D) となる。
以下、$ Q の約数のペアのうち、互いに素であるようなものの個数は$ D^{\log_{2} 3} 以下となることを示す。
$ Q の素因数分解を考える。
すなわち、互いに異なる$ n 個の素数$ p_1, p_2, \ldots, p_n と$ n 個の正整数$ k_1, k_2, \ldots, k_n が存在して$ Q = \prod_{i = 1}^{n} p_{i}^{k_{i}} を満たすとする。
このとき、$ Q の約数の個数は$ D = \prod_{i = 1}^{n} (k_{i}+1) となる。
ここで、$ Q の約数$ N^{\prime} と$ M^{\prime} のペアで互いに素であるものの個数は、$ \prod_{i = 1}^{n} (2k_{i}+1) となる。
なぜなら、$ 1 \le i \le n を満たす正整数$ i について、「$ p_{i} が$ N^{\prime} と$ M^{\prime} のどちらにも含まれない」「$ p_{i} が$ N^{\prime} に$ 1 個含まれる」$ \cdots 「$ p_{i} が$ N^{\prime} に$ k_{i} 個含まれる」「$ p_{i} が$ M^{\prime} に$ 1 個含まれる」$ \cdots 「$ p_{i} が$ M^{\prime} に$ k_{i} 個含まれる」の$ 2k_{i}+1 通りが考えられるからである。
そのため、$ 1 \le i \le n を満たす任意の正整数$ i について、$ 2k_{i}+1 \le (k_{i}+1)^{\log_{2} 3} を満たすとすると、$ \prod_{i = 1}^{n} (2k_{i}+1) \le \prod_{i=1}^{n} (k_{i}+1)^{\log_{2} 3} = D^{\log_{2} 3} となる。
よって、$ k_{i} が正整数のとき、すなわち$ k_{i} \ge 1 のときに、$ 2k_{i}+1 \le (k_{i}+1)^{\log_{2} 3} であることを示せば良い。
$ k_{i} = 1 のときは、$ (k_{i}+1)^{\log_{2} 3} = 2^{\log_{2} 3} = 3 = 2k_{i}+1 より上は成り立つ。
$ k_{i} = 2 のとき、$ 2\sqrt{2} \lt 3 より$ \frac{3}{2} \lt \log_{2} 3 であるため、$ (k_{i}+1)^{\log_{2} 3} \gt 3^{\frac{3}{2}} = 3 \sqrt{3} \gt 5 = 2k_{i}+1 より上は成り立つ。
$ k_{i} \ge 3 のとき、$ \sqrt{k_{i}+1} \ge \sqrt{4} = 2 であるため、上と同様に、$ (k_{i}+1)^{\log_{2} 3} \gt (k_{i}+1)^{\frac{3}{2}} \ge 2(k_{i}+1) \gt 2k_{i}+1 となる。
よって、$ k_{i} \ge 1 のときに$ 2k_{i}+1 \le (k_{i}+1)^{\log_{2} 3} であることが示せた。
また、$ k_{i} \ge 1 において$ 2k_{i}+1 \le (k_{i}+1)^{\log_{2} 3} と$ \log_{k_{i}+1} (2k_{i}+1) \le \log_{2} 3 は同値であるため、以下のように示すこともできる。
ここで、$ 0 より大きい実数$ x に対して定義される関数$ f(x) = \log_{x+1} (2x+1) = \frac{\log (2x+1)}{\log (x+1)} を考える。
これを微分すると$ f^{\prime} (x) = \frac{(2x+2)\log (x+1) - (2x+1)\log (2x+1)}{(x+1)(2x+1)(\log (x+1))^{2}} となる。
$ \frac{2x+1}{x+1} = 2-\frac{1}{x+1} より、これは$ x が正のとき単調増加であるため、$ x \ge 1 ならば$ \frac{2x+1}{x+1} \ge \frac{3}{2} \gt \sqrt{2} である。
よって$ x \ge 1 のとき、$ (\frac{2x+1}{x+1})^{2x+1} \gt (\sqrt{2})^{2x+1} \gt 2^{x} \ge x+1 を満たす。
この不等式に$ (x+1)^{2x+1} を掛けて対数をとると、$ (2x+1)\log (2x+1) \ge (2x+2)\log (x+1) となる。
よって、$ x \ge 1 において$ f^{\prime} (x) \lt 0 となるため、$ x \ge 1 において$ f は単調減少である。
以上から、$ k_{i} \ge 1 のときに$ \log_{k_{i}+1} (2k_{i}+1) = f(k_{i}) \le f(1) = \log_{2} 3 が示せた。
ちなみに、$ Q の約数$ N^{\prime} と$ M^{\prime} のペアで互いに素であるものの個数$ \prod_{i = 1}^{n} (2k_{i}+1) は、$ Q^{2} の約数の個数と等しい。
すなわち、解説に書かれている計算量と、ここで解析した計算量は、ほぼ同等であると思われる。
解答例
下は上記の方法（コンテスト後の考察を除く）で解いたときの提出結果である。
また、上記の提出の際に提出したソースコードをその下に転記する。
code: C
int cmp_ll (const void *ap, const void *bp) {
long long a = *(long long *)ap;
long long b = *(long long *)bp;
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
int gcd (int a, int b) {
if (a <= 0 || b <= 0) {
return a+b;
}
if (a%b == 0) {
return b;
}
return gcd(b, a%b);
}
int main () {
int p = 0;
int q = 0;
int res = 0;
int ans_cnt = 0;
int tmp_cnt = 0;
int d = 0;
int div_cnt = 0;
res = scanf("%d", &p);
res = scanf("%d", &q);
d = gcd(p, q);
p /= d;
q /= d;
for (int i = 1; i*i <= q; i++) {
if (q%i == 0) {
div_cnt++;
if (q/i != i) {
div_cnt++;
}
}
}
for (int i = 0; i < div_cnt; i++) {
for (int j = 0; j < div_cnt; j++) {
if ((q/d2)%d1 == 0 && (d1+d2)%p == 0) {
long long mul = (long long) (q/(d1*d2));
mul *= (long long) ((d1+d2)/p);
tmp_cnt++;
}
}
}
if (tmp_cnt <= 0) {
printf("0\n");
return 0;
}
qsort(ans, tmp_cnt, sizeof(long long)*2, cmp_ll);
ans_cnt = 1;
for (int i = 1; i < tmp_cnt; i++) {
ans_cnt++;
}
}
printf("%d\n", ans_cnt);
for (int i = 0; i < ans_cnt; i++) {
printf("%lld %lld\n", ansi0, ansi1); }
return 0;
}
下はコンテスト後の考察を反映した方法（再帰版）で解いたときの提出結果である。
また、上記の提出の際に提出したソースコードをその下に転記する。
code: C
typedef struct list {
int v;
struct list *n;
} list;
int cmp_ll (const void *ap, const void *bp) {
long long a = *(long long *)ap;
long long b = *(long long *)bp;
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
int gcd (int a, int b) {
if (a <= 0 || b <= 0) {
return a+b;
}
if (a%b == 0) {
return b;
}
return gcd(b, a%b);
}
int func (int p, int q, int idx, int b1, int b2, int primes_cnt, list **b_inv, int ans_cnt, long long ans[]2) { if (idx >= primes_cnt) {
while (l1 != NULL) {
int d1 = l1->v;
while (l2 != NULL) {
int d2 = l2->v;
if ((d1+d2)%p == 0) {
long long mul = (long long) (q/(d1*d2));
mul *= (long long) ((d1+d2)/p);
ans_cnt++;
}
l2 = l2->n;
}
l1 = l1->n;
}
return ans_cnt;
}
ans_cnt = func(p, q, idx+1, b1, b2, primes_cnt, b_inv, ans_cnt, ans);
ans_cnt = func(p, q, idx+1, (b1|(1<<idx)), b2, primes_cnt, b_inv, ans_cnt, ans);
ans_cnt = func(p, q, idx+1, b1, (b2|(1<<idx)), primes_cnt, b_inv, ans_cnt, ans);
return ans_cnt;
}
int main () {
int p = 0;
int q = 0;
int res = 0;
int ans_cnt = 0;
int tmp_cnt = 0;
int d = 0;
int div_cnt = 0;
int tmp = 0;
int primes_cnt = 0;
res = scanf("%d", &p);
res = scanf("%d", &q);
d = gcd(p, q);
p /= d;
q /= d;
tmp = q;
for (int i = 1; i*i <= q; i++) {
if (q%i == 0) {
div_cnt++;
if (q/i != i) {
div_cnt++;
}
}
}
tmp = q;
for (int i = 2; i*i <= q; i++) {
if (tmp%i == 0) {
primes_cnt++;
while (tmp%i == 0) {
tmp /= i;
}
}
}
if (tmp > 1) {
primes_cnt++;
}
for (int i = 0; i < div_cnt; i++) {
int b = 0;
for (int j = 0; j < primes_cnt; j++) {
b |= (1<<j);
}
}
}
tmp_cnt = func(p, q, 0, 0, 0, primes_cnt, b_inv, 0, ans);
if (tmp_cnt <= 0) {
printf("0\n");
return 0;
}
qsort(ans, tmp_cnt, sizeof(long long)*2, cmp_ll);
ans_cnt = 1;
for (int i = 1; i < tmp_cnt; i++) {
ans_cnt++;
}
}
printf("%d\n", ans_cnt);
for (int i = 0; i < ans_cnt; i++) {
printf("%lld %lld\n", ansi0, ansi1); }
return 0;
}
下はコンテスト後の考察を反映した方法（約数ペアの列挙を非再帰化）で解いたときの提出結果である。
また、上記の提出の際に提出したソースコードをその下に転記する。
互いに素な約数のペアの列挙を非再帰化するにあたり、こちらの記事を参考にした。 code: C
typedef struct list {
int v;
struct list *n;
} list;
int cmp_ll (const void *ap, const void *bp) {
long long a = *(long long *)ap;
long long b = *(long long *)bp;
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
int gcd (int a, int b) {
if (a <= 0 || b <= 0) {
return a+b;
}
if (a%b == 0) {
return b;
}
return gcd(b, a%b);
}
int main () {
int p = 0;
int q = 0;
int res = 0;
int ans_cnt = 0;
int tmp_cnt = 0;
int d = 0;
int div_cnt = 0;
int tmp = 0;
int primes_cnt = 0;
res = scanf("%d", &p);
res = scanf("%d", &q);
d = gcd(p, q);
p /= d;
q /= d;
tmp = q;
for (int i = 1; i*i <= q; i++) {
if (q%i == 0) {
div_cnt++;
if (q/i != i) {
div_cnt++;
}
}
}
tmp = q;
for (int i = 2; i*i <= q; i++) {
if (tmp%i == 0) {
primes_cnt++;
while (tmp%i == 0) {
tmp /= i;
}
}
}
if (tmp > 1) {
primes_cnt++;
}
for (int i = 0; i < div_cnt; i++) {
int b = 0;
for (int j = 0; j < primes_cnt; j++) {
b |= (1<<j);
}
}
}
for (int b1 = 0; b1 < (1<<primes_cnt); b1++) {
int b2 = (1<<primes_cnt)-1;
while (b2 >= 0) {
list *l1 = NULL;
b2 &= b1;
while (l1 != NULL) {
int d1 = l1->v;
while (l2 != NULL) {
int d2 = l2->v;
if ((d1+d2)%p == 0) {
long long mul = (long long) (q/(d1*d2));
mul *= (long long) ((d1+d2)/p);
tmp_cnt++;
}
l2 = l2->n;
}
l1 = l1->n;
}
b2--;
}
}
if (tmp_cnt <= 0) {
printf("0\n");
return 0;
}
qsort(ans, tmp_cnt, sizeof(long long)*2, cmp_ll);
ans_cnt = 1;
for (int i = 1; i < tmp_cnt; i++) {
ans_cnt++;
}
}
printf("%d\n", ans_cnt);
for (int i = 0; i < ans_cnt; i++) {
printf("%lld %lld\n", ansi0, ansi1); }
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_368_B
提出のURL 提出時刻 結果 備考
感想
コンテスト中は、かなり悩んでしまった。A問題が解けてからB問題が解けるまで90分以上かかっているが、その間はずっとB問題で行き詰まっていたことになる。$ NM が$ Q の約数なら話は簡単だったのだが、$ NM 自体は$ Q の倍数になることがわかったので、$ Q の約数だけ調べれば良いという簡単な話ではなさそうだった。実は調べるべき$ N の範囲はある程度絞れるのではないかと、条件の式を変形しながら探ってはみたものの、いろいろ試した結果、特にそんなことはなさそうなことがわかり、途方に暮れていた。
そんななか、$ N と$ M の最大公約数を考えたとき、どう約分できるかということを、ふと考え始めて、ようやく道は開けたかな。といっても、手元のメモを見る限り、その後もしばらく悩んでいたようではあるが。正解を提出できたのも、これの二十数分後であるので、そこまですんなりはいかなかったらしい。
コンテスト後の考察についても、$ f^{\prime} (x) の分子の計算を誤り、$ (x+1)\log (x+1) - (2x+1)\log (2x+1) だと勘違いしていたため、負になるのは明らかだと考えていた。これを書いている最中に間違いに気づき、どう証明するか悩んだが、なんとか証明できてよかった。ただ、もしかしたら他にもどこか間違っているかもしれない（もしかしたら計算量の結論も）
上について、わざわざ導関数の正負を確認しなくても証明できる方法があったため、「解き方」の記述を修正した。