ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=404152 方針 制約が大きい…JavaならBigIntegerを使えばよいかもしれない。 2^32より大きいmodを使うとlong longでもoverflowする可能性があるので 10^5((10^5)^2 >= 10^9.6≒2^32)程度のmodを素…

蟻本他を参考にした。 modの逆元 与えられたa,b,mから ax≡b(mod m) を満たすxを求めたいとする。 このとき ay≡1(mod m) なるyが求まれば y*ax≡y*b(mod m) x≡y*b(mod m)(∵ay≡1)としてxを求めることができる。 ay≡1(mod m)⇔∃k(ay=1+km)であるから変形して ay-m…