#include <iostream> using namespace std; const int maxFn = 1458; // 18 * 81; const unsigned long long limit = 1000000000000000000L; // 10 ^ 18 const unsigned long long maxK = limit / maxFn; // avoid exceeding long limit int squares[10]; unsigned int f(unsigned long long n) { unsigned long long reminder = n; unsigned int sum = 0; while (reminder > 0) { sum += squares[(int) (reminder % 10)]; reminder = reminder / 10; } return sum; } int main() { for (int i = 0; i < 10; i++) { squares[i] = i * i; } ios::sync_with_stdio(false); unsigned long long k, a, b, result = 0; cin >> k; cin >> a; cin >> b; // Optimize input values if (k > a) a = k; if (k < b / maxFn) { // equivalent of: if (k * maxFn < b) b = k * maxFn; b = (k >= maxK) ? limit : (k * maxFn); } // n must be divisible with no rest by k unsigned long long start = (a % k == 0) ? a : (a + k - (a % k)); unsigned long long end = (b % k == 0) ? b : (b - (b % k)); // Find matching n for (unsigned long long n = start; n <= end; n += k) { if (k * f(n) == n) { result += 1; } } cout << result << endl; 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 | #include <iostream> using namespace std; const int maxFn = 1458; // 18 * 81; const unsigned long long limit = 1000000000000000000L; // 10 ^ 18 const unsigned long long maxK = limit / maxFn; // avoid exceeding long limit int squares[10]; unsigned int f(unsigned long long n) { unsigned long long reminder = n; unsigned int sum = 0; while (reminder > 0) { sum += squares[(int) (reminder % 10)]; reminder = reminder / 10; } return sum; } int main() { for (int i = 0; i < 10; i++) { squares[i] = i * i; } ios::sync_with_stdio(false); unsigned long long k, a, b, result = 0; cin >> k; cin >> a; cin >> b; // Optimize input values if (k > a) a = k; if (k < b / maxFn) { // equivalent of: if (k * maxFn < b) b = k * maxFn; b = (k >= maxK) ? limit : (k * maxFn); } // n must be divisible with no rest by k unsigned long long start = (a % k == 0) ? a : (a + k - (a % k)); unsigned long long end = (b % k == 0) ? b : (b - (b % k)); // Find matching n for (unsigned long long n = start; n <= end; n += k) { if (k * f(n) == n) { result += 1; } } cout << result << endl; return 0; } |