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
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <limits>
#include <array>

using Number = unsigned long long;

class NumberWitoutZeros
{
  static const unsigned N = 19;
  std::array<unsigned, N> numbers;
  unsigned usedDigits{0};

public:
  NumberWitoutZeros(Number n)
  {
    translateToWithoutZeros(n);
  }

  NumberWitoutZeros& operator=(Number n)
  {
    translateToWithoutZeros(n);
    return *this;
  }

  void translateToWithoutZeros(Number n)
  {
    int i = 0;
    while (n)
    {
      unsigned digit = n % 10;
      n /= 10;
      numbers[i++] = digit;
    }
    usedDigits = i;
  }

  Number getNumber()
  {
    Number sum{0};
    for (unsigned i{usedDigits-1}; ; --i)
    {
      sum *= 10;
      sum += numbers[i];
      if (!i)
      {
        return sum;
      }
    }
  }

  bool operator<=(Number n)
  {
    return getNumber() <= n;
  }

  NumberWitoutZeros& operator++()
  {
    bool shift{true};
    unsigned i{0};
    while(shift && i < N)
    {
      if (++numbers[i] == 10)
      {
        numbers[i] = 0;
      }
      else
      {
        shift = false;
      }
      ++i;
    }
    usedDigits = std::max(usedDigits, i);
  }

  Number f()
  {
    Number sum{0};
    for (unsigned i{0}; i < usedDigits; ++i)
    {
      sum += numbers[i] * numbers[i];
    }
    return sum;
  }
};

bool operator==(Number n1, NumberWitoutZeros n2)
{
  return n1 == n2.getNumber();
}

unsigned doTask(NumberWitoutZeros start, Number end, Number k)
{
  Number count{0};
  while (start <= end)
  {
    //std::cout << start.f() * k << " ? " << start.getNumber() << "\n";
    if (start.f() * k == start)
    {
      ++count;
    }
    ++start;
  }
  return count;
}

unsigned doTask2(Number start, Number end, Number k)
{

}

int main()
{
  std::ios_base::sync_with_stdio(0);
  Number k;
  Number a;
  Number b;
  std::cin >> k >> a >> b;

  NumberWitoutZeros start {a};

  std::cout << doTask(start, b, k) << "\n";
  //std::cout << doTask2(a, b, k) << "\n";

}