AtCoder ABC300
3完。敗北すぎる。かろうじて緑パフォーマンスで、レーティングは茶色のまま。
簡単すぎて合わせて10分以内。このことがDでの油断を誘うことに。
結局解けなかった。
- 素因数と個数をmapにつっこむ
- 各素因数に対して、個数が消費される値を計算。7が3個なら、7 14 21なので21。
- その中で一番大きい値がN
で組んだがACの方が少ない。解説見る前に明日すっきりした頭でもう一度考えよう。
苦手なmod問題のためスキップ。atcoderlib modintの使い方を早く覚えなければ。
【競プロライブラリ】mint(modint)で学ぶC++ - Qiita
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
- 多倍長整数を素で扱えない言語（C++とか）に対する不公平さをなくすため。
- 998244353に10^9に近い素数という以上の意味はないようだ。
- 足し算、掛け算などは後からmodでも、式の途中でmodでも結果が変わらない。
- 引き算はマイナスをプラスに直す処理が必要。
- 割り算だけややこしい。逆元を求める。逆元の存在が、pとmが互いに素なこととあるので、このために素数を指定しているもよう。
- 足し算等なら自分で書けばいいが、割り算が面倒なのでatcoderlib modintを使うべき。
- modint998244353などが容易されていてべんり。
解説を読んだが、かなり近いところまで迫ってはいた。
考察
- N, M, Q ~ 10^5。ダイクストラと違って負のコストが扱え、閉路が検出できる（と鉄則本で復習した）Bellman-FordはO(NM)×クエリー数Qなので全然無理そう。Warshall-FloydもO(N^3)なので全然無理。
- Union-Find（DSU）でつながっていない判定はできる。root()がO(logN)なので計算量的にもこれっぽい。
- 閉ループは0なら問題。0以外ならどちか回りで必ずinf。
ここに、graph[N+1][]とdist[N+1]で探索を加えればよかったのか。
あとlong long int の上限に近いINFはlong long int INF = 2LL << 60;とLLが必要。
