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
#include <cstdio>

using namespace std;

const long long int BRUTE_THRESHOLD = 25*1000*1000;

const long long int SPECIAL = 1000LL*1000*1000*1000*1000*1000;
long long int K, A, B;
long long int count = 0;


//Clever: #######################################################

int f(int* digCount) {
	return \
	digCount[1] + \
	4  * digCount[2] + \
	9  * digCount[3] + \
	16 * digCount[4] + \
	25 * digCount[5] + \
	36 * digCount[6] + \
	49 * digCount[7] + \
	64 * digCount[8] + \
	81 * digCount[9];
}

void genDigCountFromN(int* digCount, long long int n) {
	for (int i=0; i<18; ++i) {
		++digCount[n%10];
		n/=10;
	}
}

bool digCountsEqual(int* digCount1, int* digCount2) {
	for (int i=0; i<10; ++i) {
		if (digCount1[i] != digCount2[i])
			return false;
	}
	return true;
}

void checkMask(unsigned c) {
	int digit=0;
	int digCount[10]={};
	int digCountN[10]={};
	
	for (unsigned i = 1; i < (1<<27); i<<=1) {
		if (c&i)
			++digit;
		else
			++digCount[digit];
	}
	
	//Calculate n from a set of digits:
	long long int n = K * f(digCount);
	
	if (!(A<=n && n<=B))
		return;
	
	//Check if digits match:
	genDigCountFromN(digCountN, n);
	
	if (digCountsEqual(digCount, digCountN))
		++count;
}

void clever() {
	//Iterating over subsets of given size:
	//Gosper's hack: http://stackoverflow.com/a/15934122
	unsigned c = (1LL<<9)-1;
	while (c < (1LL<<27)) {
		checkMask(c);
		unsigned a = c&-c, b = c+a;
		c = (c^b)/4/a|b;
	}
	
	//Special check for n=10^18 :
	if (K==SPECIAL && A<=SPECIAL && SPECIAL<=B) {
		++count;
	}
}

//Brute: #######################################################

long long int f(long long int n) {
	long long int res = 0;
	while (n!=0) {
		res += (n%10)*(n%10);
		n /= 10;
	}
	return res;
}

void brute() {
	long long int start = (A/K)*K;
	if (start<A) start += K;
	
	long long int end = (B/K)*K;
	
	for (long long int i=start; i<=end; i+=K) {
		if (K*f(i) == i) {
			++count;
		}
	}
}

//Main: #######################################################

int main() {
	scanf("%lld %lld %lld", &K, &A, &B);
	
	if ((B-A)/K > BRUTE_THRESHOLD)
		clever();
	else
		brute();
	
	printf("%lld\n", count);
	
	return 0;
}