Как найти количество чисел, которые делятся на 7?

Question

Учитывая целое число N, как эффективно найти количество чисел, которые делятся на 7 (их обратная сторона также должна делиться на 7) в диапазоне:

• [0, 10^N - 1]

Пример:

Для N=2, ответ:

• 4 {0, 7, 70, 77}

[Все числа от 0 до99, которые делятся на 7 (также их обратное делится)]

Мой подход, простая грубая сила:

• инициализировать счет в ноль
• запустить циклс i=0 до конца
• если a(i) % 7 == 0 && reverse(a(i)) % 7 == 0, то мы увеличиваем счет

Примечание:

• reverse(123) = 321, reverse(1200) = 21,например!

Answer 1

Пусть COUNTS (n, f, r) будет числом n-значных чисел, таким что n% 7 = f и REVERSE (n)% 7 = r

Подсчет легко рассчитать для n = 1 :

COUNTS (1, f, r) = 0 , когда f! = R , так как однозначное число совпадает с его обратным.

COUNTS (1, x, x) = 1 при x> = 3 и

COUNTS (1, x, x) = 2 при x <3 </strong>, так как 7% 3 = 0, 8% 3 = 1 и 9% 3 = 2

Подсчет для других длин можно выяснить, рассчитав, что происходит, когда вы добавляете каждую цифру от 0 до 9 к числам, характеризуемым предыдущими подсчетами.

В конце, COUNTS (N, 0,0) - это ответ, который вы ищете.

Например, в python это выглядит так:

def getModCounts(len):
    counts=[[0]*7 for i in range(0,7)]
    if len<1:
        return counts
    if len<2:
        counts[0][0] = counts[1][1] = counts[2][2] = 2
        counts[3][3] = counts[4][4] = counts[5][5] = counts[6][6] = 1
        return counts
    prevCounts = getModCounts(len-1)
    for f in range(0,7):
        for r in range(0,7):
            c = prevCounts[f][r]
            rplace=(10**(len-1))%7
            for newdigit in range(0,10):
                newf=(f*10 + newdigit)%7
                newr=(r + newdigit*rplace)%7
                counts[newf][newr]+=c
    return counts

def numFwdAndRevDivisible(len):
    return getModCounts(len)[0][0]

#TEST
for i in range(0,20):
    print("{0} -> {1}".format(i, numFwdAndRevDivisible(i)))

Посмотрите, даст ли он ответы, которые вы ожидаете. Если нет, возможно, есть ошибка, которую мне нужно исправить:

0 -> 0
1 -> 2
2 -> 4
3 -> 22
4 -> 206
5 -> 2113
6 -> 20728
7 -> 205438
8 -> 2043640
9 -> 20411101
10 -> 204084732
11 -> 2040990205
12 -> 20408959192
13 -> 204085028987
14 -> 2040823461232
15 -> 20408170697950
16 -> 204081640379568
17 -> 2040816769367351
18 -> 20408165293673530
19 -> 204081641308734748

Это довольно хороший ответ, если считать до N разумно - способ лучше, чем грубая сила, что считаетсядо 10 ^ N.

Для очень длинных отрезков, таких как N = 10 ^ 18 (вас, вероятно, спросят мод счета 1000000007 или что-то в этом роде), есть ответ следующего уровня.

Обратите внимание, что существует линейная зависимость между счетчиками для длины n и счетчиками для длины n + 1 , и что эта взаимосвязь может быть представлена ​​матрицей 49x49. Вы можете возвести эту матрицу в степень к N -й степени, используя возведение в степень путем возведения в квадрат умножения матрицы O (log N), а затем просто умножить на счет одной цифры, чтобы получить число N.

Answer 2

Давайте посмотрим, что происходит в моде 7, когда мы добавляем цифру d к префиксу abc.

10 * abc + d =>
  (10 mod 7 * abc mod 7) mod 7 + d mod 7

reversed number:

abc + d * 10^(length(prefix) =>
  abc mod 7 + (d mod 7 * 10^3 mod 7) mod 7

Обратите внимание, что нам нужно только количество префиксов abc mod 7для каждого такого остатка, а не фактические префиксы.

Answer 3

Существует рекурсивное решение, использующее метод цифр dp для любых цифр.

long long call(int pos , int Mod ,int revMod){
    if(pos == len ){
        if(!Mod && !revMod)return 1;
        return 0;
    }
    if(dp[pos][Mod][revMod] != -1 )return dp[pos][Mod][revMod] ;

    long long res =0;
    for(int i= 0; i<= 9; i++ ){
        int revValue =(base[pos]*i + revMod)%7;
        int curValue = (Mod*10 + i)%7;
        res += call(pos+1, curValue,revValue) ;
    }

    return dp[pos][Mod][revMod] = res ;
}