如何找到可以被7整除的数字计数？

问题描述

给出一个整数 N ，如何有效地找到以下范围内被7整除的数（它们的倒数也应被7整除）：

Given an integer N, how to efficiently find the count of numbers which are divisible by 7 (their reverse should also be divisible by 7) in the range:

• [0，10 ^ N-1]

• [0, 10^N - 1]

示例：

对于 N = 2 ，答案：

• 4 {0，7，70，77}

• 4 {0, 7, 70, 77}

[从0到99的所有数字都可以被7整除（也可以将它们的反数整除）]

[All numbers from 0 to 99 which are divisible by 7 (also their reverse is divisible)]

我的方法，简单的暴力破解：

My approach, simple brute-force:

• 将计数初始化为零


• 从 i = 0 到结束


• 如果 a（i）％7 == 0& ;& reverse（a（i））％7 == 0 ，然后我们增加计数

• initialize count to zero
• run a loop from i=0 till end
• if a(i) % 7 == 0 && reverse(a(i)) % 7 == 0, then we increase the count

注意：

• reverse（123）= 321 ， reverse（ 1200）= 21 ，例如！

• reverse(123) = 321, reverse(1200) = 21, for example!

推荐答案

使用数字dp技术对任何数字进行递归的解决方案。

There is a recursive solution using digit dp technique for any digits.

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 ;
}

这篇关于如何找到可以被7整除的数字计数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！