【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_JUDGEchar 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");elseprintf("0\n");else if(x==y)if(z==y)printf("2\n");elseprintf("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; }

转载于:https://www.cnblogs.com/ywwyww/p/9204661.html

总结

以上是生活随笔为你收集整理的【XSY3048 】Polynominal 数学的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。