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
#include<limits.h>
#include<stdio.h>
#include<cmath>

int main(int argc, char* argv[]) {
  unsigned long int a, b, k, result;
  unsigned long int sum, val, n, digit, i, digit_count;
  scanf("%lu %lu %lu", &k, &a, &b);

  for(i = (a/k)*k; i <= b; i+=k) {
    sum=0;
    n=i;
    while(n) {
      val = n/10;
      digit = n - 10*val;
      sum += digit*digit;
      n = val;
    }
    if(sum*k==i) {
      ++result;
    }

    if(i > 1000000) {
      for( digit_count = 5; digit_count < ULONG_MAX; digit_count++) {
        if(std::pow(10, digit_count) > b) {
          break;
        }
      }

      if(i >= digit_count*81) {
        printf("%lu\n", result);
        return 0;
      }
    }
  }

  printf("%lu\n", result);
  return 0;
}