題目描述

　　給你三個正整數 \(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 数学的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。