Expert.
Put your skills to the test.

Problem summary

In base b, rot(A) moves the first digit of the ordinary positive representation of A to its end. For each of four positive base-b integers M, find the smallest positive A satisfying rot(A)−A=M, or output 0 if none exists. Digits above nine are A through F.

Constraints

2 < b ≤ 16; every M has at most 10,000 base-b digits.

Worked example

Official sample, transcribed with whitespace restored from the PDF.

10
216
1318
2349
44444

135
0
1372
0

Solution analysis

1. Write A=d·b^k+q with first digit d and k trailing digits, allowing leading zeros within q. Then rot(A)−A=(b−1)q−d(b^k−1). Because b^k−1 is divisible by b−1, M must be divisible by b−1. Perform this division directly on the input digit string.
2. Put C=M/(b−1). For a chosen k, the equation forces q=C+d·R_k, where R_k=1+b+⋯+b^(k−1), the k-digit repunit. A valid q must be below b^k. If any first digit works for this length, d=1 also works and gives its smallest answer. A shorter length is always smaller than a longer length, so find the smallest k with C+R_k<b^k.
3. If C has D digits, k cannot be below D. Test k=D by adding the repunit with ordinary base-b carries; if it overflows, k=D+1 always works since b≥3. Prefix the resulting padded k digits with 1. For M=216 in base ten, C=24 and q=24+11=35, producing 135.

Why it works

The algebra gives a necessary and sufficient formula for q at each length and first digit. Divisibility by b−1 is necessary; when it holds, choosing a sufficiently long repunit yields a valid q. At fixed k, increasing d increases both q and A, so d=1 is optimal and succeeds whenever any digit succeeds. No k<D fits C, and at k=D+1, C<b^D and R_k=(b^(D+1)−1)/(b−1), whose sum is below b^(D+1) for b≥3. Testing these two lengths therefore finds the global minimum.

Watch out. Do not parse M into a machine integer. Keep trailing-part zeros when concatenating. Divisibility is by the decimal integer b−1, while the input digits are base b.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
using namespace std;
int value(char c){
    return c<='9'?c-'0':c-'A'+10;
}
char digit(int x){
    return x<10?char('0'+x):char('A'+x-10);
}
string addRepunit(string number,int length,int base){
    number=string(length-int(number.size()),'0')+number;
    int carry=0;
    for(int i=length-1;i>=0;--i){
        int sum=value(number[i])+1+carry;
        number[i]=digit(sum%base);
        carry=sum/base;
    }
    return carry?string():number;
}
int main(){
    int base;
    cin>>base;
    for(int test=0;test<4;++test){
        string m,quotient;
        cin>>m;
        int remainder=0;
        for(char c:m){
            int current=remainder*base+value(c);
            int q=current/(base-1);
            remainder=current%(base-1);
            if(q||!quotient.empty()){
                quotient.push_back(digit(q));
            }
        }
        if(remainder){
            cout<<0<<'\n';
            continue;
        }
        if(quotient.empty()){
            quotient="0";
        }
        // At most one extra trailing digit is needed.
        string suffix=addRepunit(quotient,int(quotient.size()),base);
        if(suffix.empty()){
            suffix=addRepunit(quotient,int(quotient.size())+1,base);
        }
        cout<<'1'<<suffix<<'\n';
    }
}