[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\].

样例输入 SampleInput

1 2 5

样例输出 SampleOutput

1

Codeforces 493E

代码 Code

数学题，依然是有点不懂。首先各种特判，然后将 \[b\] 转成 \[a\] 进制表示得到可能的系数将 \[t\] 代入验证即可。

我看到有人说可以参考这篇文章于是我把它翻译了下 ->[译] 输入两个数确定一个多项式，当然我是建议去看原文的。。。

#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;
}