No.3022 一元一次式 mod 1000000000
解説AC。だが、解説を読んだ後も混乱した。
整数論の問題なので、2と5に分解してどうにかするしかない。Mに2や5の素因子が多いとダメそう……というところから、整数解が存在する条件が得られる。
すると、両辺を2や5で出来る限り割ることで、
・N'*k+M'=0(mod d')
という形の式になり、N'とd'は互いに素になる。なので、オイラーの定理を使って-M'/N'の値を求めることができる。
この値が0になるのは、そもそもM'がd'の倍数のとき。なので、N*kがd'の倍数になれば良い。N'とd'は互いに素なので、このときはd'が答え。
No.3024 全単射的
自力AC。
二部マッチングだからフロー！ と思ったが、うまくグラフが構築できず、よく考えたらUnion-findで解けると気付きAC。
しかし、公式解説の解法はフローで解いていた。景品だけでなく、人の方も頂点にすると思いつけなかった。
0 件のコメント:
コメントを投稿