yukicoder contest 302 参戦記 - Qiita

yukicoder contest 302 参戦記 いつもはだいたい途中でギブアップするのだけど、今回は2問解いた時点で残り10分とかそんなんだった……. どっちも瞬殺できないといけなかった……. A 1578 A × B × C 実際に計算してみると K=1 は A'=BC, B'=AC, C'=AB で (ABC)2、K=2 は A''=A2BC, B''=AB2C, C''=ABC2 で (ABC)4 となり、(ABC)2K であることはすぐ見当がつく. K≦1012 なので 2K は計算できない. 繰り返し二乗法で解けないかと考えてドツボにはまってしまったが、フェルマーの小定理により ABC109+7-1≡1 (mod 109+7) なので 2K を 109+7-1 で割った余りを求めればいいだけだった. $ python Python 3.8.9 (default, May 5