2 条题解
-
0
#include<bits/stdc++.h> //by: hansang.睡醒版 using namespace std; typedef long long LL; const int N=30, M=110; LL f[N][M], K, a[N]; //可以写少一维，因为主要看的不是大小而是余数 LL calc(LL x){ if(x==0) return 1; int len=0; LL ans=0, sum=0; //sum是前缀和%K的余数 while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ //含有前导零 for(int j=0; j<=a[i]-1; j++){ ans+=f[i-1][(2*K-sum-j%K)%K]; //sum[len, i+1],f[i-1, 1],j就是当前i选的值 if(i==1 && (sum+j)%K==0) ans++; //当i==1时整个数的余数为零 } sum=(sum+a[i])%K; if(i==1 && sum==0) ans++; //同上 } return ans; } int main(){ //freopen("a.in", "r", stdin); LL a, b; while(scanf("%lld%lld%lld", &a, &b, &K)!=EOF){ memset(f, 0, sizeof(f)); for(int i=0; i<=9; i++) f[1][i%K]++; for(int t=2; t<=25; t++){ for(int i=0; i<=9; i++){ for(int j=0; j<K; j++) f[t][(i+j)%K]+=f[t-1][j]; } } printf("%lld\n", calc(b)-calc(a-1)); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:58:35
#include<bits/stdc++.h> //by: hansang.睡醒版 using namespace std; typedef long long LL; const int N=30, M=110; LL f[N][M], K, a[N]; //可以写少一维，因为主要看的不是大小而是余数 LL calc(LL x){ if(x==0) return 1; int len=0; LL ans=0, sum=0; //sum是前缀和%K的余数 while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ //含有前导零 for(int j=0; j<=a[i]-1; j++){ ans+=f[i-1][(2*K-sum-j%K)%K]; //sum[len, i+1],f[i-1, 1],j就是当前i选的值 if(i==1 && (sum+j)%K==0) ans++; //当i==1时整个数的余数为零 } sum=(sum+a[i])%K; if(i==1 && sum==0) ans++; //同上 } return ans; } int main(){ //freopen("a.in", "r", stdin); LL a, b; while(scanf("%lld%lld%lld", &a, &b, &K)!=EOF){ memset(f, 0, sizeof(f)); for(int i=0; i<=9; i++) f[1][i%K]++; for(int t=2; t<=25; t++){ for(int i=0; i<=9; i++){ for(int j=0; j<K; j++) f[t][(i+j)%K]+=f[t-1][j]; } } printf("%lld\n", calc(b)-calc(a-1)); } return 0; }
- 1
