#include <bits/stdc++.h> using namespace std; typedef long long int LL; LL k; set<LL> znalezione; short cyfry[10]; short cyfry2[10]; LL qpot(LL a, short b) { if (!b) return 1; LL x=qpot(a, b>>1); x *= x; if (b&1) return x*a; return x; } bool licz(LL ret) { while (ret) { cyfry2[ret%10]--; ret/=10; } for (short i=1; i<10; i++) if (cyfry2[i]) return false; return true; } void solve(int cyfra, int left) { if (!left--) return; short c,i; LL num; for (c=cyfra; c<10; c++) { num = 0; for (i=1; i<10; i++) num += i*i*(cyfry2[i] = cyfry[i]); num *= k; if (licz(num)) znalezione.insert(num); cyfry[c]++; solve(c, left); cyfry[c]--; } } template<typename __T> size_t operator-(_Rb_tree_const_iterator<__T> it1, _Rb_tree_const_iterator<__T> it2) { if (it1==it2) return 0; // if (it2>it1) return -(it2-it1); // ommited size_t ret = 1; while (--it1 != it2) ret++; return ret; } LL f(LL x) { return znalezione.upper_bound(x)-znalezione.begin(); } int main() { LL a,b; scanf("%lld%lld%lld", &k, &a, &b); solve(1, 18); printf("%lld\n", f(b)-f(a-1)); 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 | #include <bits/stdc++.h> using namespace std; typedef long long int LL; LL k; set<LL> znalezione; short cyfry[10]; short cyfry2[10]; LL qpot(LL a, short b) { if (!b) return 1; LL x=qpot(a, b>>1); x *= x; if (b&1) return x*a; return x; } bool licz(LL ret) { while (ret) { cyfry2[ret%10]--; ret/=10; } for (short i=1; i<10; i++) if (cyfry2[i]) return false; return true; } void solve(int cyfra, int left) { if (!left--) return; short c,i; LL num; for (c=cyfra; c<10; c++) { num = 0; for (i=1; i<10; i++) num += i*i*(cyfry2[i] = cyfry[i]); num *= k; if (licz(num)) znalezione.insert(num); cyfry[c]++; solve(c, left); cyfry[c]--; } } template<typename __T> size_t operator-(_Rb_tree_const_iterator<__T> it1, _Rb_tree_const_iterator<__T> it2) { if (it1==it2) return 0; // if (it2>it1) return -(it2-it1); // ommited size_t ret = 1; while (--it1 != it2) ret++; return ret; } LL f(LL x) { return znalezione.upper_bound(x)-znalezione.begin(); } int main() { LL a,b; scanf("%lld%lld%lld", &k, &a, &b); solve(1, 18); printf("%lld\n", f(b)-f(a-1)); return 0; } |