yukicoder No.3002 & No.3003 解説

類題である京大2023理系数学大問1の問2を解説しているとある動画を思い出したので、簡単に解けました。

解説

問題リンク
No.3002(easy) No.3003(hard)
問題は「$(Ax^B) mod (x^2+x+1)$ を求めよ.」というものでした。
hardになると $|A|$ と $B$ が大きくなります。
まず、$x^2+x+1 \equiv 0 \pmod {x^2+x+1}$ であることは明らかなので、両辺に $x-1$ を掛けます。すると、$x^3-1 \equiv 0 \pmod {x^2+x+1}$ → $x^3 \equiv 1 \pmod {x^2+x+1}$ となります。
本題に戻ります。$Ax^B = Ax^{3*\lfloor \frac{B}{3} \rfloor}Ax^{Bmod3}$ と変形でき、これは $mod(x^2+x+1)$ だと $Ax^B \equiv Ax^{Bmod3}$ となるので、これの右辺を考えればよいです。
(Ⅰ) $Bmod3 = 0$ の時、右辺は $A$ となります。なので、0 Aが答えです。
(Ⅱ) $Bmod3 = 1$ の時、右辺は $Ax$ となります。なので、A 0が答えです。
(Ⅲ) $Bmod3 = 2$ の時、右辺は $Ax^2$ となります。これは $x^2+x+1$ で割ると、余りは $-Ax-A$ となり、-A -Aが答えとなります。
計算量は $O(1)$ となります。
コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
	ll A, B;
	cin >> A >> B;
	if(B % 3 == 0) {
		cout << "0 " << A << endl;
	}
	else if(B % 3 == 1) {
		cout << A << " 0" << endl;
	}
	else {
		cout << -A << ' ' << -A << endl;
	}
}

yukicoderはThe・数学という問題が沢山あるので、もっと解いていきたいです