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
// Łukasz Proksa, Silesian University of Technology, Poland

// Potyczki Algorytmiczne 2015, trial round
// Task "Równanie"
// Solved! O(30 000)

#include <iostream>
using namespace std;

typedef long long LL;

#define FOR(i, b, e) for(int i = (b); i <= (e); ++i)
#define MIN(a, b) ((a) < (b) ? (a) : (b))

static const int MAX_SUM = 1458;
bool isSum[1459];

LL a, b, k;

int f(LL n)
{
  int sum = 0;
  while (n > 0LL) { // O(18)
    int d = (int)(n % 10LL);
    sum += d*d;
    n /= 10LL;
  }
  return sum;
}

int main()
{
  ios_base::sync_with_stdio(false);

  FOR(i, 0, MAX_SUM) {
    isSum[i] = true;
  }
  isSum[1350]=0;isSum[1355]=0;isSum[1363]=0;isSum[1365]=0;isSum[1366]=0;
  isSum[1367]=0;isSum[1371]=0;isSum[1372]=0;isSum[1374]=0;isSum[1380]=0;
  isSum[1382]=0;isSum[1383]=0;isSum[1384]=0;isSum[1387]=0;isSum[1388]=0;
  isSum[1389]=0;isSum[1391]=0;isSum[1395]=0;isSum[1397]=0;isSum[1398]=0;
  isSum[1399]=0;isSum[1400]=0;isSum[1401]=0;isSum[1403]=0;isSum[1404]=0;
  isSum[1405]=0;isSum[1406]=0;isSum[1408]=0;isSum[1410]=0;isSum[1411]=0;
  isSum[1412]=0;isSum[1414]=0;isSum[1415]=0;isSum[1416]=0;isSum[1417]=0;
  isSum[1418]=0;isSum[1419]=0;isSum[1420]=0;isSum[1421]=0;isSum[1422]=0;
  isSum[1423]=0;isSum[1425]=0;isSum[1427]=0;isSum[1428]=0;isSum[1429]=0;
  isSum[1430]=0;isSum[1431]=0;isSum[1432]=0;isSum[1433]=0;isSum[1434]=0;
  isSum[1435]=0;isSum[1436]=0;isSum[1437]=0;isSum[1438]=0;isSum[1439]=0;
  isSum[1440]=0;isSum[1442]=0;isSum[1443]=0;isSum[1444]=0;isSum[1445]=0;
  isSum[1446]=0;isSum[1447]=0;isSum[1448]=0;isSum[1449]=0;isSum[1450]=0;
  isSum[1451]=0;isSum[1452]=0;isSum[1453]=0;isSum[1454]=0;isSum[1455]=0;
  isSum[1456]=0;isSum[1457]=0;

  cin>>k>>a>>b;

  LL first = a/k + (LL)(a % k != 0); // ceil(a / k)
  if (first > (LL)MAX_SUM) {
    cout<<"O"<<endl;

    return 0;
  }
  int st = (int)first;
  int last = (int)MIN((LL)MAX_SUM, b/k); // floor(b / k)
  int cnt = 0;
  
  FOR(sum, st, last) { // for each 'sum', such that a <= k*sum <= b is satisfied
    if (!isSum[sum]) {
      continue;
    }
    LL n = k*(LL)sum;
    if (f(n) == sum) {
      cnt++;
    }
  }
  cout<<cnt<<endl;

  return 0;
}