# [Codeforces493E] Vasya and Polynomial

## 描述 Description

Vasya is studying in the last class of school and soon he will take exams. He decided to study polynomials. Polynomial is a function \[P(x)=a_0+a_1x^1+..+a_nx^n\]. Numbers \[a_i\] are called coefficients of a polynomial, non-negative integer \[n\] is called a degree of a polynomial.

Vasya has made a bet with his friends that he can solve any problem with polynomials. They suggested him the problem: “Determine how many polynomials \[P(x)\] exist with integer non-negative coefficients so that \[P(t)=a\], and \[P(P(t))=b\], where \[t\], \[a\] and \[b\] are given positive integers”?

Vasya does not like losing bets, but he has no idea how to solve this task, so please help him to solve the problem.

## 输入格式 InputFormat

The input contains three integer positive numbers \[t\], \[a\], \[b\] no greater than \[10^{18}\].

## 输出格式 OutputFormat

If there is an infinite number of such polynomials, then print “inf” without quotes, otherwise print the reminder of an answer modulo \[10^9+7\].

1 2 5

1

Codeforces 493E

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
ll i,j,t,n,m,l,r,k,z,y,x;
ll a,b,ans;
int main()
{
scanf("%I64d%I64d%I64d",&t,&a,&b);
if (t==1)
{
if (a==1)
{
if (a==b) printf("inf\n");
else printf("0\n");
return 0;
}
else if (b>=a)
{
while (b%a==0) b/=a;
if (b==1)
{
printf("1\n");
return 0;
}
}
}
ans=(a==b)?1:0;
x=z=0;y=1;
if (t<=a)
{
while (b)
{
x=b%a;
b/=a;
z+=y*x;
y*=t;
}
}
if (z==a) ans++;
printf("%I64d\n",ans);
return 0;
}``````