题解 P3996【Number】
还是放一份代码吧，我的博客里应该说得比较清楚了，粘贴过来。
T2:Number
解法一
暴力计算数列，然后搜索可能的答案。
复杂度 O(2^L)
L为数列长度。
预计得分 40
解法二
当a！=1时，注意到以下性质：
A(0)=1 A(i)=2A(i-1) (即A(i)=2^n)
这个数列增长得非常快，以至于每一项都大于之前所有项的和。
这个数列是除了 b=0且A(0)=0 时增长得最慢的一个，意味着其他所有数列都满足数列的每一项都大于之前所有项的和这样一个性质。
这样就是一个贪心，预处理一下，每次减去小于等于n的最大项，如果最后n可以被减到0意味着原来的n可以被表示，反之一定不行。
对于b=0且A(0)=0的数列特判就可以了。
单次复杂度O(logn)
当a=1时，这个数列是一个等差数列，并且可以被表示成以下形式：
{A(0)+b,A(0)+2b,A(0)+3b,......,A(0)+Nb,......}
如果n可以被表示为其中若干个不同项的和，那么显然有：
关于x，y的方程 A(0)x+by=n
存在一组正整数解，使得y>=(x(x+1))/2。
解得的方程的意义是数列中选了x项，并且每一项的b的系数之和为y。
很明显，只有y>=(x(x+1))/2时y才能拆分成若干个互不相同的自然数。
A(0)=0或b=0时要特判。解方程时要特别小心，直接解A(0)x+by=n得到的x可能是负数，要找它为正数的解。
单次复杂度O(logn)
总体复杂度O(Tlogn)
预计得分 100
码风略丑。
#include<cstdio>
#include<cstring>
typedef long long ll;
ll T,n,a,b,x0;
ll num[1000];
ll extended_euclid(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll n=extended_euclid(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-static_cast<ll>(a/b)*y;
return n;
}
bool linear_equation(ll a,ll b,ll c,ll &x,ll &y)
{
ll n=extended_euclid(a,b,x,y);
if(c%n) return false;
ll k=c/n;
x*=k;
y*=k;
return true;
}
ll gcd(ll a,ll b)
{
return (a%b==0)?b:gcd(b,a%b);
}
bool cacl()
{
ll x=0,y=0;
if(!linear_equation(x0,b,n,x,y)) return false;
ll G=gcd(b,x0);
ll b1=b/G,x01=x0/G;
if(x<0)
{
ll gmp1=y%x01,gmp2=(y-y%x01)/x01;
y=gmp1;
x=x+gmp2*b1;
}
if(x<0) return false;
ll tmp1=x%b1,tmp2=(x-x%b1)/b1;
if(tmp1==0) tmp2--,tmp1+=b1;
ll tmp3=y+tmp2*x01,tmp4=1ll*(tmp1*(tmp1+1))/2;
if(tmp4<=tmp3) return true;
else return false;
}
int main()
{
ll ans=0;
scanf("%d",&T);
while(T--)
{
memset(num,0,sizeof(num));
scanf("%lld%lld%lld%lld",&x0,&a,&b,&n);
if(n==0) ans+=(x0==0&&b==0);
else if(x0==0&&b==0) ans+=(n==0);
else if(a==1&&b==0)
{
if(x0==0) ans+=(n==0);
else if(!(n%x0)) ans++;
}
else if(a==1&&x0==0)
{
if(b==0) ans+=(n==0);
else if(!(n%b)) ans++;
}
else if(a==1)
{
if(cacl()) ans++;
}
else
{
int x=1;
num[0]=x0;
while(1)
{
num[x]=1ll*num[x-1]*a+b;
if(num[x]>=n) break;
x++;
}
for(int i=x;i>=1;i--)
if(n>=num[i]) n-=num[i];
if(n==0) ans++;
}
}
printf("%lld",ans);
return 0;
}