#include <iostream> #include <cstdio> #include <ctime> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #include <utility> #include <fstream> #include <cassert> #define INF 999999999999999999LL #define MOD 1000000007 #define MAX 10010 #define SMTH 12 #define ALL 50 #define DEBUG false using namespace std; long long check(long long n) { long long tmpSum = 0; while (n != 0) { int rest = n % 10; tmpSum += (rest * rest); n -= rest; n /= 10; } return tmpSum; } int main() { long long k,a,b; scanf("%lld %lld %lld", &k, &a, &b); bool filled[MAX]; for (int i = 0; i < MAX; i++) filled[i] = false; filled[0] = true; for (int t = 0; t < 18; t++) { bool tmp[MAX]; for (int i = 0; i < MAX; i++) tmp[i] = filled[i]; for (int i = 1; i <= 9; i++) { for (int j = 0; j < MAX; j++) { if (filled[j] && (j + i*i < MAX)) { tmp[j + i*i] = true; } } } for (int i = 0; i < MAX; i++) filled[i] = tmp[i]; } int res = 0; for (long long i = 0; i <= 1459; i++) { if (filled[i]) { if ((i * k >= a) && (i * k <= b) && (i == check(i * k))) res++; } } printf("%d", res); return 0; }
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 | #include <iostream> #include <cstdio> #include <ctime> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #include <utility> #include <fstream> #include <cassert> #define INF 999999999999999999LL #define MOD 1000000007 #define MAX 10010 #define SMTH 12 #define ALL 50 #define DEBUG false using namespace std; long long check(long long n) { long long tmpSum = 0; while (n != 0) { int rest = n % 10; tmpSum += (rest * rest); n -= rest; n /= 10; } return tmpSum; } int main() { long long k,a,b; scanf("%lld %lld %lld", &k, &a, &b); bool filled[MAX]; for (int i = 0; i < MAX; i++) filled[i] = false; filled[0] = true; for (int t = 0; t < 18; t++) { bool tmp[MAX]; for (int i = 0; i < MAX; i++) tmp[i] = filled[i]; for (int i = 1; i <= 9; i++) { for (int j = 0; j < MAX; j++) { if (filled[j] && (j + i*i < MAX)) { tmp[j + i*i] = true; } } } for (int i = 0; i < MAX; i++) filled[i] = tmp[i]; } int res = 0; for (long long i = 0; i <= 1459; i++) { if (filled[i]) { if ((i * k >= a) && (i * k <= b) && (i == check(i * k))) res++; } } printf("%d", res); return 0; } |