c++ - Count numbers in range divisible by K with a sum of digits in range -

i have such task:

let's call number "lucky" if divisible k , sum of digits lays in [p, q]. count quantity of "lucky" numbers in [a, b].

1 ≤ a, b < 10^11,
1 ≤ p, q ≤ 99,
1 ≤ k ≤ 10^11.

time each test - 5 seconds

here code

#include <iostream> #include <fstream> using namespace std;  int sum; long long k; int number[10]; int digits[10]; int p; int q; long long a; long long b; int delta; bool flag = false; long long memory[100000][100][10][2];  long long pow (int a, int b) {     long long res = 1;     for(int = 0; < b; i++)         res *= a;     return res; } int sumofdigits(long long number) {     int sum = 0;     while(number != 0)     {         sum += number % 10;         number /= 10;     }     return sum; } long long tolong(int digits[], int n) {     long long sum = 0;     for(int = 0; < n; i++)     {         sum *= 10;         sum += digits[i];     }     return sum; } long long function(long long remainder// remainder of division k,                       int currsum // current sum of digits,                        int n //number of digit added,                        bool alldigitsallowed //says if digits can added number) {     if(n == 10)     {         int counter = 0;         for(int = p; <= q; i++)         {              long long res = - currsum + remainder;             if(res%k == 0 && (alldigitsallowed || i-currsum <= number[9]))             {                 counter++;                 if(!alldigitsallowed && number[9] == i-currsum)                     flag = true;             }         }         return counter;     }     long long res = 0;     int temp = 0;     while(currsum + temp <= q)     {            long long tempremainder = (temp*pow(10,10-n)+remainder)%k;         if(temp == number[n-1] && !alldigitsallowed)         {             if(tempremainder < 100000)             {                 if(memory[tempremainder][currsum+temp][n+1][false] == -1)                     memory[tempremainder][currsum+temp][n+1][false] = function(tempremainder, currsum + temp, n+1,false);                 res += memory[tempremainder][currsum+temp][n+1][false];             }             else                 res += function(tempremainder, currsum + temp, n+1,false);             //res += function(tempremainder, currsum + temp, n+1,false);             break;         }         else         {             if(tempremainder < 100000)             {                 if(memory[tempremainder][currsum+temp][n+1][true] == -1)                     memory[tempremainder][currsum+temp][n+1][true] = function(tempremainder, currsum + temp, n+1,true);                 res += memory[tempremainder][currsum+temp][n+1][true];             }             else                 res += function(tempremainder, currsum + temp, n+1,true);         }         temp++;     }     return res; }  long long f (long long a) {     flag = false;     memset(&number, 0, sizeof(number));     sum = 0;     int = 9;     while(a != 0)     {         number[i] = a%10;         /= 10;         i--;     }     for(int j = 0; j < 10; j++)         swap(number[j],number[9-j]);     return function(0,0,1,false); }  int main() {     ifstream in("lucky.in");     ofstream out("lucky.out");     in >> k >> p >> q >> >> b;     sum = p;     memset(&memory, -1, sizeof(memory));     long long result = - f(a) + flag;     memset(&memory, -1, sizeof(memory));     out<< result + f(b) << endl;     return 0; } 

in solution try make number determined sum of digits, adding digits 1 one. problem can't memorize the remainders of division k.

so how can deal problem?

i use like:

unsigned int compute_number_sum(uint64_t n) {     unsigned int res = 0;      while (n != 0) {         const uint64_t nd = n / 10;         res += static_cast<unsigned int>(n - 10 * nd); // equivalent res += n % 10         n = nd;     }     return res; }  uint64_t count_lucky_number(uint64_t a, uint64_t b, uint64_t k,                              unsigned int p, unsigned int q) {     uint64_t res = 0;     const uint64_t min_i = (a + k - 1) / k * k;     (uint64_t = min_i; <= b; += k) {         const unsigned int numbersum = compute_number_sum(i);         res += p <= numbersum && numbersum <= q;     }     return res; }