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
#include <stdint.h>
#include <iostream>
#include <algorithm>

using namespace std;


int64_t sqsum(int64_t i) {
  int r = 0;
  
  while(i) {
    int d = i % 10; i /= 10;
    r += d * d;
  }
  
  return r;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int64_t a, b, k;
  cin >> k >> a >> b;
  
  int d = 0;
  int64_t m = 0;
  while(81 * d >= m / k and m <= b / 9) {
    d += 1;
    m = 10 * m + 1;
  }
  b = min(b, 9 * m);
  
  b = min(b, 1458 * k);
  
  if(a > b) {
    cout << "0\n";
    return 0;
  }
  
  int i0 = (a + k - 1) / k;
  int i1 = b / k;
  
  int r = 0;
  for(int i = i0; i < i1; ++i) {
    if(i == sqsum(k * i)) ++r;
  }
  
  cout << r << '\n';
  
  return 0;
}