http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_f
http://omochan.hatenablog.com/entry/2017/10/20/004232の続きです。
普通に蟻本通りにやればいいだけでした…。
x≡k(modm)
x≡k'(modm')を満たすxは
x=mt+kとして
mt≡k'-k(modm')をtについて解けばいいだけでした。k,m,k',m'がすべて10^9より小さければ、xはオーバーフローせずに求められます。
具体的にはmt'≡g(modm')(g=gcd(m,m'))となるt'(modm')を求めてからt=(k'-k)/g*t'とすればいいだけです。
modの基本定理のおさらい。
- g|Mのときga≡gb(modM)<=>a≡b(modM/g)
- gとMが互いに素の時,ga≡gb(modM)<=>a≡b(modM)
二つとも両辺に寄せてからg(a-b)=Mtとかすれば導出できます。これが一番modの中で基礎となる式かもしれない。modの積と商の変形ルールを述べています。
ちなみに和(と差)は当たり前ですが、
a≡b(modM)<=>a+c≡b+c(modM)です。
四則演算の変形+中国剰余定理でだいぶmodは使いやすくなった?
ll phi(ll M) {
ll A = M;
for(ll i = 2; i * i <= A; i++) {
if(A % i == 0) {
M = M / i * (i - 1);
while(A % i == 0) A /= i;
}
}
if(A != 1) M = M / A * (A - 1);
return M;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll extgcd(ll a, ll b, ll& x, ll& y) { //get(ax + by = gcd(a, b))
if(b == 0) {
x = 1; y = 0;
return a;
}
ll res = extgcd(b, a % b, y, x);
y -= (a / b) * x;
return res;
}
ll mod_pow(ll a, ll n, ll mod) { //get a^n mod
if(n == 0) return 1;
ll res = mod_pow(a, n / 2, mod);
if(n % 2 == 0) return res * res % mod;
else return a * res % mod * res % mod;
}
ll mod_inv(ll a, ll m) { //get x such that ax=gcd(a, m)(modm)
ll x, y;
extgcd(a, m, x, y);
return (x % m + m) % m;
}
int Q;
ll A, M;
ll loop(ll A, ll M) {
if(M == 1) return 10000;
ll K = loop(A, phi(M));
ll tK = mod_pow(A, K, M);
return tK + (tK < 100 ? M : 0);
}
void solve() {
cin >> Q;
while(Q--) {
cin >> A >> M;
ll pM = phi(M);
ll K = loop(A, M) % M;
ll pK = loop(A, pM) % pM;
ll pt = mod_inv(M, pM);
ll g = gcd(M, pM), l = M * pM / g;
ll t = ((pK - K) / g * pt) % pM;
//debug(M, pM, K, pK, pt, g, l, t);
ll pans = ((t * M % l + K) % l + l) % l;
ll ans = pans < 100 ? pans + l : pans;
cout << ans << "\n";
//debug(mod_pow(A, ans, M), ans % M);
}
}
