/*
 * File:   main.cpp
 * Author: Yue
 *
 * Created on March 22, 2015, 5:00 AM
 *
 * By visual inspection:
4 x 1738 = 6952
4 x 1963 = 7852
12 x 483 = 5796
18 x 297 = 5346
21 x 474 = 9954 x
27 x 198 = 5346 x
28 x 157 = 4396
39 x 186 = 7254
42 x 138 = 5796 x
48 x 159 = 7632
 */

#include <cstdlib>
#include <stdio.h>
#include <math.h>

using namespace std;

// Need to write global array, because pow function is for floats and causes
// errors when converting to int
int power[7] = {1, 10, 100, 1000, 10000, 100000, 1000000};

bool ternaryGood( int multiplicand, int multiplier, int product ) {
    int length[3];
    if( multiplier > 9 ) length[0]=2;
    else length[0]=1;
    for( int i=1;i<5;i++ ) {
        if( multiplicand<pow(10,i) ) {
            length[1]=i;
            break;
        }
    }
    for( int i=4;i<8;i++ ) {
        if( product<pow(10,i) ) {
            length[2]=i;
            break;
        }
    }
    if( length[0]+length[1]+length[2]!=9 )
        return false;

    int digit[9];
    //printf("%d * %d = %d\n", multiplier, multiplicand, product);
    //printf("%d . %d . %d\n", length[0], length[1], length[2]);

    for( int i=0;i<length[1]-1; i++ ) {
        digit[i] = multiplier/10;
        multiplier -= digit[i]*10;
    }
    digit[length[0]-1] = multiplier;

    for( int i=0;i<length[1]-1; i++ ) {
        int paw = power[length[1]-i-1];
        digit[length[0]+i] = multiplicand/paw;
        multiplicand -= digit[length[0]+i]*paw;
        //printf("Multiplicand: %d + %d * %d\n", multiplicand, digit[length[0]+i], paw);
    }
    digit[length[0]+length[1]-1] = multiplicand;

    for( int i=0;i<length[2]-1; i++ ) {
        int paw = power[length[2]-i-1];
        digit[length[0]+length[1]+i] = product/paw;
        product -= digit[length[0]+length[1]+i]*paw;
    }
    digit[length[0]+length[1]+length[2]-1] = product;

    int sum = 0;
    int prod = 1;
    if( sum!=45 || prod!=362880 )
        return false;
    return true;
}

int main(int argc, char** argv) {

    // Multiplicand WLOG can be assumed bigger than multiplier
    // Product is at least 1234, at most 7 digits (i.e. 9876543)
    // Multiplier is between 1 and 98
    // Multiplicand is between 1 and 9876

    int multiplicand;
    int multiplier;
    int product;
    int sum = 0;
    int count = 0;

    for( multiplier=1; multiplier<98; multiplier++ ) {
        for( multiplicand=1234/multiplier; multiplicand<9876; multiplicand++ ) {
            product = multiplicand * multiplier;
            count++;
            if( product > 9876543 )
                break;
            else if( ternaryGood(multiplicand, multiplier, product) ) {
                sum += product;
                printf( "%d x %d = %d, %d\n", multiplier, multiplicand, product, sum );
            }
        }
    }

    return 0;
}