【XSY3048 】Polynominal 数学

题目描述

　　给你三个正整数 \(a,b,c\)，求有多少个系数均为非负整数的多项式 \(f(x)\) 满足 \(f(a)=b\) 且 \(f(b)=c\)

　　\(a,b,c\leq {10}^{18}\)

题解

　　先把一堆情况判掉，接下来只考虑 \(a<b<c\) 的情况。

　　当 \(a\neq 1\) 时，多项式的每一项的系数都 \(<b\)。设 \(c=(c_1c_2\ldots c_n)_b\)，那么唯一可能符合要求的多项式就是 \(f(x)=\sum_{i=0}^{n-1}c_{n-i}x^i\)。只需要判断 \(f(a)\) 是不是等于 \(b\) 就行了。

　　当 \(a=1\) 时，类似的，只有 \((\sum_{i=1}^nc_i)=1\) 或 \(b\) 时有满足要求的多项式。

　　时间复杂度：\(O(\log V)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<functional>

#include<cmath>

//using namespace std;

using std::min;

using std::max;

using std::swap;

using std::sort;

using std::reverse;

using std::random_shuffle;

typedef long long ll;

typedef unsigned long long ull;

typedef std::pair<int,int> pii;

typedef std::pair<ll,ll> pll;

void open(const char *s){

#ifndef ONLINE_JUDGE

	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}

int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}

void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}

int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}

int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}

const ll p=998244353;

ll a1[100010];

int main()

{

	open("a");

	ll x,y,z;

	while(~scanf("%lld%lld%lld",&x,&y,&z))

	{

		if(x==1&&y==1)

			if(z==1)

				printf("infinity\n");

			else

				printf("0\n");

		else if(x==y)

			if(z==y)

				printf("2\n");

			else

				printf("0\n");

		else if(y==z)

				printf("1\n");

		else if(x>y||y>z)

			printf("0\n");

		else if(x==1)

		{

			for(int i=1;i<=100;i++)

				a1[i]=0;

			int t1=0;

			ll a=z;

			while(a)

			{

				a1[++t1]=a%y;

				a/=y;

			}

			ll sum=0;

			for(int i=1;i<=100;i++)

				sum+=a1[i];

			if(sum==y||sum==1)

				printf("1\n");

			else

				printf("0\n");

		}

		else

		{

			for(int i=1;i<=100;i++)

				a1[i]=0;

			int t1=0;

			ll b=z;

			while(b)

			{

				a1[++t1]=b%y;

				b/=y;

			}

			int s=1;

			ll s1=0,s2=1;

			for(int i=1;i<=t1;i++)

			{

				s1+=s2*a1[i];

				s2*=x;

			}

			s=(s1==y);

			printf("%d\n",s);

		}

	}

	return 0;

}

巴特西

【XSY3048 】Polynominal 数学

题目描述

题解

代码

最新文章

热门文章