必要な知識
- 整数Aの約数の個数の求め方
- 約数の総積の求め方
- modのあれこれ
私は掛け算もできない小卒父と掛け算くらいはできる高卒母の元で生まれ育った凡々々人でございますので、Atcoderの解説はとても難しくほとんど理解できません。
ですから、私のようにお困りの方がほんのり理解できるように、理解したことを共有したいと思いますので、温かい目でご一読いただければ幸いです。
整数Aの約数の個数の求め方
こちらの解説はネット上にいくらでもあるわけですが、問題を解くのに何が必要かすら分からない身といたしましては、散らばった知識を集めることすら一苦労です。
念のため共有しますが、副題をコピペして検索いただいても結構です。
例）
$180 = 2^2 ・ 3^2 ・ 5^1$
上記は180を素因数分解したときの例です。
この時、180の約数の総数はそれぞれの素因数の指数に1を加えた値を掛け算することで、以下のように求めることができます。
$(2 + 1)(2 + 1)(1 + 1) = 18$
それぞれの素因数の指数の選び方は
$2^{0, 1, 2}$の3パターン
$3^{0, 1, 2}$の3パターン
$5^{0, 1}$の2パターン
ありますから、これらを組み合わせたときに得られるパターンの総数は、$3・3・2=18$(通り)になります。
例えば、指数に$(0, 2, 1)$を選ぶと
$2^0・3^2・5^1=45$という約数が得られます。
指数に着目して約数を列挙するとちゃんと18通りあります。
$(0, 0, 0)=2^0・3^0・5^0=1$
$(1, 0, 0)=2^1・3^0・5^0=2$
$(0, 1, 0)=2^0・3^1・5^0=3$
・・・
$4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180$
一般化すると整数Aは素因数分解したときの素数P, 指数eを用いて
$A = P_{1}^{e_{1}}・P_{2}^{e_{2}}・・・P_{n}^{e_{n}}$
と書けます。
また、Aの約数の個数Cは先ほどの具体例より
$C = (e_{1} + 1)(e_{2} + 1)・・・(e_{n} + 1)$
と表せます。
約数の総積の求め方
いま整数Aの約数の総数を求めましたが、整数Aの約数の総積は、Aの約数の総数から求めることができます。
まず総積$X$は先ほど列挙した約数を掛け合わせることで求めます。
$X=1・2・3・4・・・ 45・60・90・180$
ただ単純に上記のように求めても構いませんが、もっといいやり方があります。
$X=1・2・3・4・・・ 45・60・90・180$
$X=180・90・60・45・・・ 4・3・2・1$
Xを逆から掛け合わせると、180を約数の個数乗した値に置き換えることができます。
$1・180=180$
$2・90=180$
$3・60=180$
$X^2=180・180・180・180・・・ 180・180・180・180 = 180^{18}$
求めたいのは総積$X$ですから、両辺を$\frac{1}{2}$乗しまして$(X > 0)$
$X=180・180・・・180・180 = 180^{9}$
180の約数の総積を求めたいときは、180を$\frac{180の約数の個数}{2}$乗すればいいことがわかりました。
一般化すると整数Aの約数の総積Xは、整数Aの約数の個数Cを用いて
$X = A^{\frac{1}{2}C}$
と書き表すことができます。
ここで問題文を見てみる。
$A^B$の正の約数の総積は$A$で最大何回割り切れますか。
制約から割り切れる回数が有限回であることが示せるので、その答えを998244353で割ったあまりを求めてください。$2≤A≤10^{12}$
$0≤B≤10^{18}$
入力は全て整数
まずは「998244353で割ったあまりを求めてください。」という要求を拒否します。
その上で、$A^B$の正の約数の総積を求めるため、$A^B$の約数の個数を求めます。
$A = P_{1}^{e_{1}}・P_{2}^{e_{2}}・・・P_{n}^{e_{n}}$
と表せたので、$A$の両辺をB乗すると
$A^B = P_{1}^{Be_{1}}・P_{2}^{Be_{2}}・・・P_{n}^{Be_{n}}$
となります。
以下はB乗したらそうなるっけ？('Д')の人用です。
$60 = 2^2・3^1・5^1$ これを3乗します。
$60^3 = (2^2・3^1・5^1)^3=2^2・3^1・5^1・2^2・3^1・5^1・2^2・3^1・5^1= 2^{2+2+2}・3^{1+1+1}・5^{1+1+1}= 2^6・3^3・5^3$
$A^B$はAを素因数分解したときのそれぞれの指数にBを掛けたら求まり、Aを何乗したところで素因数が増えることはないので、$A^B$の約数の個数はAの時と同様に、その指数を使えば求めることができます。
つまり$A^B$の約数の個数Cは
$C = (Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)$
と書き表すことができます。
約数の個数が求まれば、約数の総積も求めることができました。
$X = A^{\frac{1}{2}C}$
こちらの式を使いますと、今回$A$は$A^B$でCは分かっているので総積$X$は
$X = {(A^{B})}^{\frac{1}{2}C}=A^{\frac{1}{2}BC}=A^{\frac{1}{2}B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)}$
と表すことができます。
$A^{\frac{1}{2}B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)}$自体が総積で、Aで何回割り切れますか？という問いですから、$2^4$が2で4回割り切れるのと同様に、$A^{\frac{1}{2}B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)}$はAで${\frac{1}{2}B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)}$回割り切ることができます。
現時点で、Bは入力として与えられます。
eはAを素因数分解したときのそれぞれの指数ですから、入力A,Bからやるべきことは大体イメージができてきたかなと思います。
最大の問題はBの桁が大きく、掛け算したら桁あふれしてしまうことです。最初に無視した「998244353で割ったあまりを求めてください。」を思い出して、次に出てくるmodを使い、大きな数を制限しながら計算していきます。
modのあれこれ
modとは何ぞやという方は一緒にネットで調べていきましょう！
私は忘れるのが大得意でして、忘れてはググりまた忘れてはググりの輪廻の世界を生きています。
とりあえず以下の3つが問題を解くのに必要な知識でした。
(a%pはaをpで割った余り)
1. (A + B) % P = ((A % P) + (B % P)) % P
2. (A * B) % P = ((A % P) * (B % P)) % P
3. A = 2Pq + rの理解
1.の証明
AをPで割った商をq1, 余りをr1とすると
$A = q_{1}P + r_{1}$
同様に、BをPで割った商をq2, 余りをr2とすると
$B = q_{2}P + r_{2}$
2式を足し合わせると
$A + B = q_{1}P + q_{2}P + r_{1} + r_{2} = (q_{1} + q_{2})P + r_{1} + r_{2}$
両辺についてPで割った余りを考えると、$(q_{1} + q_{2})P$はPを約数に持つので余りは0となり
$A + B ≡ r_{1} + r_{2}(\bmod P)$
r1とr2はそれぞれAをPで割った余り(=A%P)とBをPで割った余り(=B%P)なので、1.が成立する。
2.の証明
AをPで割った商をq1, 余りをr1とすると
$A = q_{1}P + r_{1}$
同様に、BをPで割った商をq2, 余りをr2とすると
$B = q_{2}P + r_{2}$
2式を掛け合わせると
$A ・ B = q_{1}q_{2}P^2 + q_{1}Pr_{2} + q_{2}Pr_{1}+ r_{1}r_{2} = (q_{1}q_{2}P + q_{1}r_{2} + q_{2}r_{1})P + r_{1}r_{2}$
両辺についてPで割った余りを考えると、$(q_{1}q_{2}P + q_{1}r_{2} + q_{2}r_{1})P
$はPを約数に持つので余りは0となり
$A・B ≡ r_{1}r_{2}(\bmod P)$
r1とr2はそれぞれAをPで割った余り(=A%P)とBをPで割った余り(=B%P)なので、2.が成立する。
1.と2.より総積をAで割れる回数をmodを使って計算する。
何度も登場しますが、総積をAで割れる回数は以下の式で求めることができました。
${\frac{1}{2}B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)}$
$0≦B≦10^{18}$ですから、1.式を使って、数を制限しながら計算する必要があります。
$(Be_{1}+1)$だけに着目して考えると
(B * e1 + 1) % P = ((B % P) * (e1 % P) % P + 1) % P
上記を計算し、さらに$B・(Be_{1}+1)$の%Pを求め、その結果と$(Be_{2}+1)$の積の%Pを求め、を繰り返していくことで、Aの素因数分解をしながら回数をP(=998244353)で割った余りを求めることができます。
と思いきや注意点がありまして、回数の式には$\frac{1}{2}$が含まれていますから、${B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)}$が奇数だった際に割り切れない数が出てくる可能性があります。
もし割り切れないのに、%Pを使って計算を進めていくと求めたい答えにはなりません。
例）$\frac{63}{2}$を3で割った余りを求めたい。
つまり31.5の整数部を3で割った余りが答えになるので
$31 ≡ 1(\bmod 3)$より1が答えになります。
先に63 % 3を計算すると余りが0になり、それを2で割った結果は0になりますから、求めたい答えと違っていることがわかります。
そこで、次のmodの性質を利用して計算を進めていきます。
A = 2Pq + rの理解
回数は${\frac{1}{2}B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)}$より、分母が必ず2になりまして、分子が偶数か奇数かによって、割り切れるか否かが変わってきます。
問題ではP(=998244353)となっていますが、2Pで割った余りがどうなるのかに着目して式変形を行います。
$B' = B(Be_{1}+1)(Be_{2}+1)・・・(Be_{n}+1)$とおく
整数Aを2P(=998244353*2)で割った商をq, 余りをrとすると
$A = 2Pq + r$ $(0≦r＜2P)$
両辺を2で割ると
$\frac{A}{2} = Pq + \frac{r}{2}$ $(0≦\frac{r}{2}＜P)$
両辺をPで割った余りを考えると、PqをPで割ったときの余りは0なので
$\frac{A}{2} ≡\frac{r}{2}(\bmod P)$
今回、Aに該当する部分がB'となっていますので、$\frac{B'}{2}$（回数）をPで割った余りを求めたいときは、$\frac{r}{2}$を求めればよく、$\frac{r}{2}$はPより小さいことが保証されているので、Aを2Pで割った余り(=r)を2で割った整数部分が求める答えとなります。
例）
今回Pは998244353ですが、値が大きいので代わりに3を用います。2P=6です。
%3の列は分数を計算し整数部分を3で割った余りを入れる。
%6の列は分子を6で割った余りを入れる。
| $\frac{A}{2}$\mod | $\frac{A}{2}$%3(求めたい) | A%6 | $\frac{A％6}{2}$(整数部) |
|---|---|---|---|
| $\frac{3}{2}$ | 1 | 3 | 1 |
| $\frac{6}{2}$ | 0 | 0 | 0 |
| $\frac{9}{2}$ | 1 | 3 | 1 |
| $\frac{12}{2}$ | 0 | 0 | 0 |
| $\frac{15}{2}$ | 1 | 3 | 1 |
| $\frac{18}{2}$ | 0 | 0 | 0 |
| $\frac{21}{2}$ | 1 | 3 | 1 |
| $\frac{24}{2}$ | 0 | 0 | 0 |
つまり、以下の列が等しくなります。
| $\frac{A}{2}$%P(求めたい) | = | $\frac{A％2P}{2}$(整数部) |
|---|
コーディング
以下のコードはTLEします。
ここまで読んでいただいた方は、ご自分で考えて実装するのをお勧めします。
#include <iostream>
using namespace std;
using ull = unsigned long long int;
#define MOD (998244353 * 2)
ull a, b;
int main() {
cin >> a >> b;
ull ans = b % MOD;
//素因数分解しながら総積をAで割った回数modを求める
for(ull i = 2; i <= a; i++) {
ull e = 0;
while(a % i == 0) {
e++;
a /= i;
}
//分子Aを2Pで割ったあまりを求める
if(e) {
ans *= (((b % MOD) * (e % MOD)) % MOD + 1) % MOD;
ans %= MOD;
}
}
//最後にA/2が答え
cout << ans / 2 << endl;
return 0;
}
私は競プロ初心者で、まだ人生で2回しかコンテストに参加したことがないので、あまり鵜呑みにせず記事をご覧いただければ幸いです。
おわりに
記事を書いておいて言うのものなんですが、間違いがあると思います。
おかしなところがありますので、厳密おじさんや厳密おばさん（愛称）は遠慮なくご指摘いただければ幸いです。
私はすでに公式問題の解答を見て心が折れかけています。
競プロは私の様な凡人はお呼びでないんだと思います。
とりあえず、ありがとうございましたm(__)m