#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; int digits_of(uLL x) { int i = 1; for(uLL pow10 = 10; x >= pow10; pow10 *= 10, ++i); return i; } int sum_of_squared_digits(uLL num) { int sum = 0; while(num > 0) { int digit = num % 10; sum += digit*digit; num /= 10; } return sum; } vector<int> squares; void gen_sqr(int digit, int free, int sum) { for(int i = 0; i <= free; ++i, sum += digit*digit) if(digit == 9) squares.push_back(sum); else gen_sqr(digit+1, free-i, sum); } void generate_squares(int digits) { gen_sqr(0, digits, 0); } int main() { uLL k, a, b; cin >> k >> a >> b; int digits_b = digits_of(b); generate_squares(digits_b); cerr << squares.size() << endl; sort(squares.begin(), squares.end()); squares.resize(unique(squares.begin(), squares.end()) - squares.begin()); uLL res = 0; for(int sum : squares) { uLL num = k * sum; if(num >= k && a <= num && num <= b && sum == sum_of_squared_digits(num)) ++res; } cout << res << endl; }
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 | #include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; int digits_of(uLL x) { int i = 1; for(uLL pow10 = 10; x >= pow10; pow10 *= 10, ++i); return i; } int sum_of_squared_digits(uLL num) { int sum = 0; while(num > 0) { int digit = num % 10; sum += digit*digit; num /= 10; } return sum; } vector<int> squares; void gen_sqr(int digit, int free, int sum) { for(int i = 0; i <= free; ++i, sum += digit*digit) if(digit == 9) squares.push_back(sum); else gen_sqr(digit+1, free-i, sum); } void generate_squares(int digits) { gen_sqr(0, digits, 0); } int main() { uLL k, a, b; cin >> k >> a >> b; int digits_b = digits_of(b); generate_squares(digits_b); cerr << squares.size() << endl; sort(squares.begin(), squares.end()); squares.resize(unique(squares.begin(), squares.end()) - squares.begin()); uLL res = 0; for(int sum : squares) { uLL num = k * sum; if(num >= k && a <= num && num <= b && sum == sum_of_squared_digits(num)) ++res; } cout << res << endl; } |