問題一覧 > 通常問題

No.1648 Sum of Powers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 26
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi 👑 ygussanyygussany
5 ProblemId : 6790 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-05 10:51:50

問題文

整数 $A,B,P,Q$ が与えられます。
ここで、ある実数 $X,Y$ が存在して以下を満たすとします。

  • $X \leq Y$
  • $X+Y=A$
  • $X \times Y=B$

このとき、 $X^N + Y^N \equiv P, X^{N-1} + Y^{N-1} \equiv Q\ (\mathrm{mod}\ 998244353 )$ を満たす $2$ 以上 $10^{18}$ 以下の整数 $N$ を $1$ つ求めてください。

なお、本問題の入力では以下が成り立つことが保証されます。

  • $X,Y$ が存在し、かつ一意に定まる。
  • $1$ 以上の整数 $N$ について $X^N+Y^N$ が整数となる。
  • 条件を満たす $2$ 以上 $10^{10}$ 以下の整数 $N$ が存在する。

入力

$A\ \ B\ \ P\ \ Q$

  • $0 \leq A,B,P,Q < 998244353$
  • 入力は全て整数

出力

$N$ を出力してください。解が複数ある場合、どれを出力しても構いません。

サンプル

サンプル1
入力
13 42 559 85
出力
3

$X=6,Y=7$ となります。よって、 $X^3+Y^3 \equiv 559 , X^2+Y^2 \equiv 85\ (\mathrm{mod}\ 998244353)$ が成立します。

サンプル2
入力
2 1 2 2
出力
1000000000000000000

$X=1,Y=1$ となり、 $1$ 以上の整数 $N$ について、 $X^N+Y^N \equiv 2\ (\mathrm{mod}\ 998244353)$ が成立します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。