#include <iostream> #include <cstdint> typedef uint64_t Uint; inline void addUpToMod0(Uint &i, Uint k) { Uint imk = i%k; i += imk == 0 ? 0 : (k - imk); } inline void getDigitsAndPow(Uint n, Uint& d, Uint &p) { p = 1; d = 1; n /= 10; while (n != 0) { p *= 10; ++d; n /= 10; } } inline Uint f(Uint n) { static Uint sq[] = {0, 1, 2*2, 3*3, 4*4, 5*5, 6*6, 7*7, 8*8, 9*9}; Uint ret = 0; while (n!=0) { Uint d = n%10; n /= 10; ret += sq[d]; } return ret; } struct Solution { Uint solve(Uint a, Uint b, Uint k) { Uint result = 0; Uint i = a, d, p; addUpToMod0(i, k); getDigitsAndPow(i, d, p); while (i <= b && d <= 19) { Uint ik = i/k; if (ik == f(i)) { ++result; /* std::clog << "* "; std::clog << i << " " << d << " " << p << std::endl; //*/ } i += k; while (i >= p*10) { p *= 10; ++d; } if (ik > d*81) { p*=10; ++d; // std::clog << "jump: " << i << " --> " << p << std::endl; i = p; addUpToMod0(i,k); // std::clog << "i: " << i << std::endl; } while (i >= p*10 && d <= 19) { p *= 10; ++d; } } return result; } }; void test(Uint a, Uint b, Uint k, Uint ex) { Uint got = Solution().solve(a,b,k); if (got != ex) { std::clog << "for ["<< a <<"," << b <<"]/" << k << " got " << got << " when expected " << ex << std::endl; } } int main() { Uint MAX = 1000000ULL*1000000ULL*1000000ULL; //* Uint k,a,b; std::cin >> k >> a >> b; Uint result = Solution().solve(a,b,k); std::cout << result << std::endl; //*/ /* test(1,MAX, 1, 1); test(10,MAX, 1, 0); test(1,MAX, 10, 1); test(1,MAX, MAX, 1); test(1,MAX-1, MAX, 0); test(5000,10000ULL, 51, 3); test(1,1,1,1); test(1,MAX,101,1); test(1,MAX,1010101,1); test(1,MAX,51,4); //*/ 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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <iostream> #include <cstdint> typedef uint64_t Uint; inline void addUpToMod0(Uint &i, Uint k) { Uint imk = i%k; i += imk == 0 ? 0 : (k - imk); } inline void getDigitsAndPow(Uint n, Uint& d, Uint &p) { p = 1; d = 1; n /= 10; while (n != 0) { p *= 10; ++d; n /= 10; } } inline Uint f(Uint n) { static Uint sq[] = {0, 1, 2*2, 3*3, 4*4, 5*5, 6*6, 7*7, 8*8, 9*9}; Uint ret = 0; while (n!=0) { Uint d = n%10; n /= 10; ret += sq[d]; } return ret; } struct Solution { Uint solve(Uint a, Uint b, Uint k) { Uint result = 0; Uint i = a, d, p; addUpToMod0(i, k); getDigitsAndPow(i, d, p); while (i <= b && d <= 19) { Uint ik = i/k; if (ik == f(i)) { ++result; /* std::clog << "* "; std::clog << i << " " << d << " " << p << std::endl; //*/ } i += k; while (i >= p*10) { p *= 10; ++d; } if (ik > d*81) { p*=10; ++d; // std::clog << "jump: " << i << " --> " << p << std::endl; i = p; addUpToMod0(i,k); // std::clog << "i: " << i << std::endl; } while (i >= p*10 && d <= 19) { p *= 10; ++d; } } return result; } }; void test(Uint a, Uint b, Uint k, Uint ex) { Uint got = Solution().solve(a,b,k); if (got != ex) { std::clog << "for ["<< a <<"," << b <<"]/" << k << " got " << got << " when expected " << ex << std::endl; } } int main() { Uint MAX = 1000000ULL*1000000ULL*1000000ULL; //* Uint k,a,b; std::cin >> k >> a >> b; Uint result = Solution().solve(a,b,k); std::cout << result << std::endl; //*/ /* test(1,MAX, 1, 1); test(10,MAX, 1, 0); test(1,MAX, 10, 1); test(1,MAX, MAX, 1); test(1,MAX-1, MAX, 0); test(5000,10000ULL, 51, 3); test(1,1,1,1); test(1,MAX,101,1); test(1,MAX,1010101,1); test(1,MAX,51,4); //*/ return 0; } |