#include <stdio.h>
#include <stdint.h>
#include <assert.h>

#define MAXLEN 14

int64_t power10tab[MAXLEN + 1];

void init_pwr10()
{
	power10tab[0] = 1;
	for (size_t i = 1; i <= MAXLEN; i++) {
		power10tab[i] = power10tab[i - 1] * 10;
	}
}

int num_len(int64_t v)
{
	// find the length of v
	int len = MAXLEN;
	for (size_t i = 0; i < MAXLEN; i++) {
		if (v < power10tab[i]) {
			len = i;
			break;
		}
	}
	assert(len < MAXLEN);
	return len;
}

// split a number at digit position {s0,s1,...} and add the numbers
// v[s0:0], v[s1:s0+1],...,v[len-1:s[last]]
// split = (1 << s0) | (1 << s1) | ...

int64_t split_num(int64_t v, int len, int split)
{
	int64_t sum = 0;
	int lastsplit = 0;
	for (int i = 0; i < len; i++) {
		if (split & 1) {
			int64_t segment = (v / power10tab[lastsplit])
				% power10tab[i + 1 - lastsplit];
			lastsplit = i + 1;
			sum += segment;
			// printf("%ld ", segment);
		}
		split >>= 1;
	}
	// last split is v[len-1:lastsplit]
	int64_t segment = (v / power10tab[lastsplit])
		% power10tab[len + 1 - lastsplit];
	sum += segment;
	// printf("%ld\n", segment);

	return sum;
}

int64_t split_test(int64_t v, int split)
{
	return split_num(v, num_len(v), split);
}

int main()
{
	init_pwr10();
	// split 6724 as {6,72,4} => 0b101
	printf("sum = %ld\n", split_test(6724, 5));
	// split 8281 as {8,2,81} => 0b110
	printf("sum = %ld\n", split_test(8281, 6));
	// split 8281 as {8281}
	printf("sum = %ld\n", split_test(8281, 0));
	// split 0
	printf("sum = %ld\n", split_test(0, 0));

	// split 10^12
	printf("sum = %ld\n", split_test(1000000LL * 1000000LL, 0));

	int64_t sum_s = 0;

	// calculate T(1000000*1000000)
	// S-numbers should be able to be splitted to 2 or more numbers, so
	// an S-number is at least 4*4
	for (int64_t i = 4; i <= 1000000; i++) {
		int64_t square = i * i;
		int L = num_len(square);
		int maxsp = 1 << L;
		// we need at least (L+1)/2 digits in the highest split
		int minsp = 1 << ((L / 2) - 1);
		for (int sp = minsp; sp < maxsp; sp++) {
			if (split_num(square, L, sp) == i) {
				printf("%ld is an S-number.\n", square);
				sum_s += square;
				break;
			}
		}
	}
	printf("The sum of S-numbers is %ld\n", sum_s);
}