Investigating Div-Sum Property Uva 11361 - c++编程基础

给定正整数a, b, k

统计在a <= n <= b的所有n中，满足n % k == 0 并且n的各个数字的和模k为0

那么首先观察，a, b的范围是int类型。

所以说a, b中肯定数字的和不会超过90.

那么k>90的时候显然直接输出0就行了。

然后可以每次都预先处理出一个三维数组

f[i][j][p] 代表的是i长度的数字，各数字之和模k余j，该数模k余p的数字个数

这个很容易

然后算某个数的时候

按位一个一个往后算就行了

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define INF 111111111  
#define MAXN 305  
#define MAXM 900005  
using namespace std;  
int f[12][111][105];  
int ten[11];  
int a, b, c;  
void ready()  
{  
    for(int i = 0; i <= 10; i++)  
        for(int j = 0; j < c && j < 90; j++)  
            for(int k = 0; k < c; k++)  
                f[i][j][k] = 0;  
    for(int i = 0; i <= 9; i++)  
        f[1][i % c][i % c]++;  
    for(int i = 2; i <= 10; i++)  
    {  
        for(int j = 0; j < c && j < 90; j++)  
        {  
            for(int k = 0; k < c; k++)  
            {  
                for(int p = 0; p < 10; p++)  
                {  
                    f[i][(j + p) % c][((k * 10) % c + p) % c] += f[i - 1][j][k];  
                }  
            }  
        }  
    }  
}  
int num[12];  
int cnt;  
int gao(int x)  
{  
    cnt = 0;  
    if(x == 0) return 1;  
    int tx = x;  
    while(tx)  
    {  
        num[++cnt] = tx % 10;  
        tx /= 10;  
    }  
    int ans = 0;  
    int m1 = 0, m2 = 0;  
    for(int i = cnt; i >




= 2; i--)  
    {  
        if(num[i] == 0) continue;  
        for(int j = 0; j < num[i]; j++)  
        {  
            int k1 = ((m1 - j) % c + c) % c;  
            int k2 = ((m2 - j * ten[i - 1] % c) % c + c) % c;  
            ans += f[i - 1][k1][k2];  
        }  
        m1 = ((m1 - num[i]) % c + c) % c;  
        m2 = ((m2 - num[i] * ten[i - 1] % c) % c + c) % c;  
    }  
    for(int i = 0; i <= num[1]; i++)  
        if(i % c == m1 && i % c == m2)  
            ans++;  
    return ans;  
}  
int main()  
{  
    ten[0] = 1;  
    for(int i = 1; i <= 9; i++) ten[i] = ten[i - 1] * 10;  
    int T;  
    scanf("%d", &T);  
    while(T--)  
    {  
        scanf("%d%d%d", &a, &b, &c);  
        if(c > 100)  
        {  
            printf("0\n");  
            continue;  
        }  
        ready();  
        printf("%d\n", gao(b) - gao(a - 1));  
    }  
    return 0;  
}