Expert.
Put your skills to the test.

Problem summary

The first term is a; each later term is the sum of squared decimal digits of its predecessor. For each test, count occurrences of v among the first n terms.

Constraints

1 ≤ T ≤ 30; 1 ≤ a,v,n ≤ 10^9.

Worked example

Official example, transcribed with whitespace restored from the PDF.

2
13 1 10
4 8 6

8
0

Solution analysis

1. The recurrence is deterministic. After the first transition every value is at most 810, because the starting value has at most ten decimal digits; later values remain in a small bounded set. Therefore a repeated term appears quickly.
2. Record each encountered value and its first index until a value repeats. This splits the generated list into a nonrepeating prefix and a cycle. Count the target in the prefix, then multiply its cycle frequency by the number of complete cycles and scan the remaining partial cycle.
3. For a=13, the sequence begins 13,10,1,1,…; the first ten terms contain eight ones. For a=4, the target 8 is absent from its first six terms.

Why it works

Before the first repeated value every generated term is explicitly recorded. Determinism implies that the subsequent values repeat the discovered cycle forever. The first n terms partition into the initial prefix, complete cycle copies, and one cycle prefix. The algorithm counts each part exactly, so their sum is the requested number.

Watch out. Count the initial value as term one, and include only the first n terms if the cycle begins later.

An independently written complete program with standard headers.

// Key idea: Before the first repeated value every generated term is explicitly recorded. Determinism
// implies that the subsequent values repeat the discovered cycle forever.
#include<algorithm>
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int nextValue(int x){
    int result=0;
    while(x!=0){
        int digit=x%10;
        result+=digit*digit;
        x/=10;
    }
    return result;
}
int main(){
    int tests;
    cin>>tests;
    while(tests--){
        int a,target;
        long long n;
        cin>>a>>target>>n;
        unordered_map<int,int>first;
        vector<int>sequence;
        int x=a;
        while(!first.count(x)){
            first[x]=static_cast<int>(sequence.size());
            sequence.push_back(x);
            x=nextValue(x);
        }
        int start=first[x];
        int length=static_cast<int>(sequence.size())-start;
        long long answer=0;
        long long prefix=min(n,static_cast<long long>(start));
        for(int i=0;i<prefix;++i){
            answer+=sequence[i]==target;
        }
        if(n>start){
            long long remaining=n-start;
            int frequency=0;
            for(int i=start;i<static_cast<int>(sequence.size());++i){
                frequency+=sequence[i]==target;
            }
            answer+=remaining/length*frequency;
            for(int i=0;i<remaining%length;++i){
                answer+=sequence[start+i]==target;
            }
        }
        cout<<answer<<'\n';
    }
}