COUNTEM - Fast Counting

Problem Link:

Contest
Practice

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”;
}
}