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
#include <iostream>
#include <vector>

using namespace std;

vector <long long> wielokrotnosc;
//Wypianie wilokrotnosci k w danym zakresie
void WypiszWielokrotnosci(long long k, long long a, long long b)
{
    long long pwielkortnosc = a/k;
    //Wyliczenie maksymalnego zakresu sumy poteg cyfr dla danego k
    short ilecyfr = 1;
    long long wynikcyfr = k*81*ilecyfr;
    for(long long i=1; i < wynikcyfr; i *= 10)
    {
        wynikcyfr = k*81*ilecyfr;
        ilecyfr++;
    }
    ilecyfr--;
    //W wypadku gdy a jest podzielne przez k
    if(!(a%k))
    {
        pwielkortnosc = pwielkortnosc * k;
        wielokrotnosc.push_back(pwielkortnosc);
        //Wypisanie wielokrotnosci
        while(pwielkortnosc + k <= b && pwielkortnosc <= wynikcyfr)
        {
            pwielkortnosc = pwielkortnosc + k;
            wielokrotnosc.push_back(pwielkortnosc);
        }
    }
    //W wypadku gdy a nie jest podzielne przez k
    else
    {
        pwielkortnosc = (pwielkortnosc + 1) * k;
        wielokrotnosc.push_back(pwielkortnosc);
        //Wypisanie wielokrotnosci
        while(pwielkortnosc + k <= b && pwielkortnosc <= wynikcyfr)
        {
            pwielkortnosc = pwielkortnosc + k;
            wielokrotnosc.push_back(pwielkortnosc);
        }
    }
}
int WypiszSumePoteg(long long n)
{
    vector <short> cyfra;
    int wynik = 0;
    //Wypisanie cyfr liczby n
    while(n >= 10)
    {
        if(n%10)
        {
            cyfra.push_back(n%10);
            n /= 10;
        }
        else{n /= 10;}
    }
    cyfra.push_back(n);
    //Dodanie poteg cyfr
    for(int i = 0; i < cyfra.size(); i++)
    {
        switch(cyfra[i])
        {
        case 1:
            wynik += 1;
            break;
        case 2:
            wynik += 4;
            break;
        case 3:
            wynik += 9;
            break;
        case 4:
            wynik += 16;
            break;
        case 5:
            wynik += 25;
            break;
        case 6:
            wynik += 36;
            break;
        case 7:
            wynik += 49;
            break;
        case 8:
            wynik += 64;
            break;
        case 9:
            wynik += 81;
            break;
        }
    }
    return wynik;
}
int SprawdzenieWyniku(long long k)
{
    int wynik = 0;
    for(int i = 0; i < wielokrotnosc.size(); i++)
    {
        if(WypiszSumePoteg(wielokrotnosc[i]) * k == wielokrotnosc[i])
        {
            wynik++;
        }
    }
    return wynik;
}
int main()
{
    //Wczytanie danych wejsciowych
    long long a, b, k;
    cin >> k >> a >> b;
    //Wypisanie wielokrotnosci k z przedzialu a-b
    WypiszWielokrotnosci(k, a, b);
    //Wypisanie ilosci wynikow
    cout << SprawdzenieWyniku(k);
    return 0;
}