cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2020 · HardDigit constraints

Next Number with Digit GCD Greater than One

National Olympiad — National round (2020 season)

Submission name: gcdd.cpp

Solve in Editor →

Problem summary

Find the smallest integer strictly greater than a very long decimal n whose digits have gcd greater than one.

Input

Positive decimal n without leading zeroes.

Output

The smallest qualifying successor.

Constraints

1 ≤ number of input digits < 1000000.

Worked example

Input and output for the worked example discussed below.

Input

34

Output

36

Solution analysis

  1. A common digit gcd greater than one has a prime factor among 2,3,5,7, since every nonzero decimal digit is at most 9. Find a successor separately using only digits divisible by each prime.
  2. For one allowed set, preserve the longest valid prefix and stop at its first forbidden digit. Increase that position to the smallest allowed greater digit, backtracking left if necessary. If all digits already qualify, begin at the last position to force strict increase.
  3. After increasing a position fill the suffix with zeroes. If no same-length successor exists, use leading p followed by zeroes. Compare the four candidates by length, then lexicographically.
  4. For 34, even digits give 40 while multiples-of-3 digits give 36, the global minimum. Zero digits are valid since gcd(0,x)=x.

Why it works

Every valid successor belongs to a prime-restricted digit set, and the rightmost feasible increase with a minimal suffix finds the smallest successor in that set.

Complexity: O(L) time and O(L) space for L input digits, with four fixed digit sets.

Watch out. Do not parse the input into a bounded integer. The successor must be strict even when n already qualifies, and may need an additional digit.

Commented C++17 solution

An independently written complete program with standard headers.

// Every valid successor belongs to a prime-restricted digit set, and the rightmost feasible increase with a
// minimal suffix finds the smallest successor in that set.
#include<iostream>
#include<string>
using namespace std;
string nextAllowed(const string&number,int prime){
    int length=number.size();
    int position=0;
    while(position<length&&(number[position]-'0')%prime==0){
        position++;
    }
    if(position==length){
        position--;
    }
    for(;position>=0;position--){
        for(int digit=number[position]-'0'+1;digit<=9;digit++){
            if(digit%prime==0){
                string answer=number.substr(0,position);
                answer+=char('0'+digit);
                answer+=string(length-position-1,'0');
                return answer;
            }
        }
    }
    return string(1,char('0'+prime))+string(length,'0');
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string number;
    cin>>number;
    string answer;
    for(int prime:{2,3,5,7}){
        string candidate=nextAllowed(number,prime);
        if(answer.empty()||candidate.size()<answer.size()||
            (candidate.size()==answer.size()&&candidate<answer)){
            answer=candidate;
        }
    }
    cout<<answer<<'\n';
}

Source: Arena Olimpiici ↗