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
// ROW
// (C)2015 Jerzy Wałaszek
//-----------------------

#include <iostream>

using namespace std;

int main()
{
  int sc[] = {0,1,4,9,16,25,36,49,64,81}; // kwadraty cyfr
  int cn[19]; // cyfry n
  int kn[19]; // cyfry k
  int i,knc=0,nnc=0,bnc=0,nsq,cnt=0,cc;
  long long k,a,b,n_min,n_max,nn,kk,bb;

  cin >> k >> a >> b;

  // Wyznaczamy pierwsze n

  if(a % k) n_min = 1 + a / k;
  else      n_min = a / k;

  // wyznaczamy liczbę cyfr b
  bb = b;
  while(bb)
  {
     bb /= 10; bnc++;
  }

  n_max = sc[9] * bnc;
  if(b / k < n_max) n_max = b / k;

  if(!n_max) cout << 0 << endl;
  else
  {
     // w tablicach cn i kn umieszczamy cyfry n i k
     kk = k;
     nn = k*n_min; // n_min jest numerem wielokrotności k
     for(i = 0; i < 19; i++)
     {
        cn[i] = nn % 10; nn /= 10; if(nn) nnc++;
        kn[i] = kk % 10; kk /= 10; if(kk) knc++;
     }

     // szukamy rozwiązań
     while(n_min <= n_max)
     {
        nsq = 0; // suma kwadratów cyfr
        for(i = 0; i <= nnc; i++) nsq += sc[cn[i]];
        if(nsq == n_min) cnt++; // rozwiązanie?
        n_min++; // następna wielokrotność k
        cc = 0;  // przeniesienie
        // w cn[] wyznaczamy cyfry następnej wielokrotności k
        for(i = 0; i <= knc; i++)
        {
          cn[i] += kn[i]+cc;
          if(cn[i] > 9)
          {
              cn[i] -= 10;
              cc = 1;
          }
          else cc = 0;
        }

        while(cc)
        {
          cn[i] += cc;
          if(cn[i] == 10) cn[i] = 0;
          else cc = 0;
          i++;
        }
        if(i > nnc) nnc = i; // nnc - liczba aktywnych cyfr w cn[]
     }
     cout << cnt << endl;  // cnt - liczba rozwiązań
  }
  return 0;
}