EXPO_COMBI Editorial

Problem Link

** PREREQUISITES**
STRINGS, IMPLEMENTATION

Explanation:

Given a string s and a decimal number k, our task is to find number of powers of k that are present in string s, we can do this simply by generating all powers of k and checking if all digits of that power are present in string s.

CodeLink:

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    long k;
    string s;
    cin>>n>>k>>s;
    int cnt_s[10]={0};
    for(char i:s)
    {
        cnt_s[i-'0']++;
    }
    long power=1;
    long maxi=(1e18);
    vector<long>ans;
    while(power<=maxi && power>0)
    {
        long temp=power;
        int cnt_a[10]={0};
        bool fl=true;
        while(temp)
        {
            int rem=temp%10;
            cnt_a[rem]++;
            temp/=10;
        }
        for(int i=0;i<10;i++)
        {
            if(cnt_a[i]>cnt_s[i])
            {
                fl=false;
                break;
            }
        }
        if(fl)
        {
            ans.push_back(power);
        }
        power*=k;
    }
    cout<<ans.size()<<"\n";
    for(auto i:ans)
    {
        cout<<i<<"\n";
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}