1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <string>
#include <vector>
#include <iostream>
using namespace std;

string lookup[200];

using llu = unsigned long long;
vector<int> results;
llu k, a, b;
int a_digits, b_digits;


llu sum_squares(llu i)
{
	llu val = i;
	llu sum = 0;
	while (val)
	{
		int t = val % 10;
		val /= 10;
		sum += t*t;
	}
	return sum;
}

void solveA(llu a, llu b, llu k)
{
	llu start = a;
	if (start <= k)
		start = k;
	else
		start += k - a % k;

	while (start <= b)
	{
		if (k * sum_squares(start) == start)
			results.push_back(1);
		start += k;
	}
}

int dig_count(llu num)
{
	int n = 0;
	while (num) {
		num /= 10;
		n++;
	}
	return n;
}

llu  max_val(llu value, int digs, int max_digs)
{
	while (digs < max_digs)
	{
		value *= 10;
		value += 9;
		++digs;
	}

	return value;
}

void solveB(llu value, llu square_sum, int digits)
{
	if (value > b)
		return;

	//sprawdz
	if (value >= a)
	{
		if (square_sum * k == value)
		{
			results.push_back(value);
		}
	}

	int new_digits = digits + 1;
	for (int i = 0; i <= 9; ++i)
	{
		llu new_value = value * 10 + i;
		if (new_value < b)
		{
			llu new_sq_sum = square_sum + i*i;

			llu m_value = max_val(new_value, new_digits, b_digits);
			llu full_sq_sum = new_sq_sum * k;
			if (full_sq_sum <= m_value)
			{
				if (sum_squares(m_value) * k >= new_value)
					solveB(new_value, new_sq_sum, new_digits);
			}
		}
	}
}

int main(void)
{
	//while (true)
	{
		cin >> k >> a >> b;
		//k = 51; a = 1; b = 1000000000000000000;
		if ((b - a) / k < 10000000)
			solveA(a, b, k);
		else
		{

			a_digits = dig_count(a);
			b_digits = dig_count(b);

			int digits = 1;
			for (int i = 1; i <= 9; ++i)
			{
				llu value = i;
				llu square_sum = value * value;
				solveB(value, square_sum, digits);
			}
		}
		cout << results.size() << endl;
		results.clear();
	}
	return 0;
}