Codeforces Round #281 (Div. 2)E（数学）_html/css_WEB-ITnose

E. Vasya と多項式

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Vasyaは勉強しています学校の最後の授業で、もうすぐ試験を受ける予定です。彼は多項式を勉強することにしました。 多項式は関数 P(x)?=?a0?+?a1x1?+?...?+?anxn です。数値 ai は多項式の係数と呼ばれ、非負の整数 n は多項式の次数と呼ばれます。

Vasya は多項式を使ってどんな問題でも解けるという賭けを友達としました。彼らは彼に問題を提案しました。「負でない整数の係数を持つ多項式 P(x) がいくつ存在するかを調べてください。そして、ここで、および b には正の整数が与えられます。」

Vasya は賭けに負けるのが好きではありませんが、まったくわかりません。このタスクの解決方法を教えてください。問題を解決するのを手伝ってください。

入力

入力には 1018 以下の 3 つの正の整数が含まれます。

出力

このような多項式が無限にある場合引用符なしで "inf" を出力します。そうでない場合は、回答のリマインダーを出力します。 modulo109?+?7.

サンプルテスト

input

2 2 2

Output

input

リーリー

アウトプット

题意：RT

思路：给出了t,a,b,那么有

f(t)=a0+a1*t+a2* t^2+...+an*t^n=a

f(a)=a0+a1*a+a2*a^2+...+an*a^n=b

a1+a2*t+...+an*t^(n-1)=(a-a0)/t

a1+a2*a+...+an*a^(n- 1)=(b-a0)/a

那么(a-a0)%t=0 && (b-a0)%a=0

a%t=a0%t && b % a=a0%a

因b>a

所以b=k*a+a0;

また因為a0<=a && a0<=b

所以a0=b%a または a0=b%a+a

这样递归求解各个常数就可了