# Problem Link:

*Author:* Nikhil Raghav

*Tester:* Nikhil Raghav

*Editorialist:* Nikhil Raghav

# Difficulty

Easy

# Problem

f(X) means sum of the digits of the number X. For example, f(12345)=1+2+3+4+5=15. Now consider the following equation:

x=a∗f(x)^b+c∗f(x)^d

You have to find the number of x, where x≤10^{18}

# Explanation

As per constraints, it is not possible to find every X, by traversing from 1 to 10^{18}. For this, we can put the value of sum of digits in the given expression. What could be the possible maximum value of sum, then? It will be 162 (9 * 18) because at every place in X we can have at max 9, and we have 18 places to be filled.

So, the number of sums in the range [1,162] satisfying the equation will be our required answer. A sum i will satisfy the equation when f(z) == i where z is a∗f(i)^b+c∗f(i)^d. We just need to count the number of z's in the range [1,162].

# Solution

## Author's Solution

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

ll poww(ll a, ll n)

{

ll res=1;

for(int i=0;i<n;i++)

res*=a;

return res;

}

ll digsum(ll x)

{

ll res=0;

while(x)

{

res+=(x%10);

x=x/10;

}

return res;

}

int main()

{

int t;

ll a,b,c,d;

cin>>t;

while(t–)

{

cin>>a>>b>>c>>d;

ll z=0, cnt=0 ;

for(ll i=0;i<=162;i++)

{

z= a*poww(i,b) + c*poww(i,d);

if(digsum(z)==i)

{

cnt++;

}

}

cout<<cnt<<"\n";

}

}