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

int sq[] = {0,1,4,9,16,25,36,49,64,81};

int main()
{
  unsigned long long k, a, b, n, p, r;
  char t[19];
  int l, i, s;

  scanf("%llu%llu%llu", &k, &a, &b);
  r = 0;
  for(n=a, n+=k-1-(n-1)%k; n<=b;)
  {
    sprintf(t, "%llu", n);
    l = strlen(t);
    for(i=p=1; i<=l; i++) p *= 10;
    for(i=s=0; i<l; i++)
    {
      if ((n/p*p+p-1)/k < s || s + (l-i)*sq[9] < n/p*p/k)
      {
        n = n/p*p+p;
        goto outer;
      }
      p /= 10;
      s += sq[t[i]-'0'];
    }
    if (n%k == 0 && n/k == s)
    {
      r++;
    }
    n++;
    outer:;
    n += k-1-(n-1)%k;
  }
  printf("%llu\n", r);
  return 0;
}