fork(2) download
copy 
  1. /*
  2.  * As discussed on StackOverflow
  3.  * http://stackoverflow.com/questions/19434497/an-algorithm-to-find-the-seed-root-of-a-given-number/19439893#19439893
  4.  */
  5.  
  6. #include<iostream>
  7. using namespace std;
  8.  
  9. typedef long long int Big_Int;
  10.  
  11. void root_stem(const Big_Int r, const Big_Int product_of_my_digits, const Big_Int target) {
  12.  
  13.         // There are two rules we can use to prune:
  14.         //
  15.         // First: The product_of_my_digits must divide into the target.
  16.         //        If not, return
  17.         // Second: The products produced lower in the search true will always be higher
  18.         //         than those above. Therefore, we should return early if
  19.         //         my_seed_product is larger than the target
  20.  
  21.         if (target % product_of_my_digits != 0)
  22.                 return;
  23.  
  24.         Big_Int my_seed_product = r * product_of_my_digits;
  25.  
  26.         if(my_seed_product >= target) {
  27.                 if (my_seed_product == target) {
  28.                         cout << r << "\t->\t" << my_seed_product << endl;
  29.                 }
  30.                 return;
  31.         }
  32.         // print all roots, with their products, between 10*r and 10*r + 9
  33.         for(Big_Int digit_to_append = 1; digit_to_append<=9; ++digit_to_append) {
  34.                 root_stem(r*10 + digit_to_append, product_of_my_digits*digit_to_append, target);
  35.         }
  36. }
  37.  
  38. int main() {
  39.         root_stem(0,1, 4977);
  40.         root_stem(0,1, 24562368);
  41.         root_stem(0,1, 176852740608);
  42.         return 0;
  43. }
  44.  
Success #stdin #stdout 0.84s 3340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
711	->	4977
79	->	4977
42643	->	24562368
4264389	->	176852740608
https://ideone.com/k2CIcM
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!