CF1985G-D-Function
题目大意
\(D(n)\) 表示 \(n\) 的数字之和。对于多少个整数 \(n\) 满足 \(10^l \le n \le 10^r\) 的条件 \(D(k \cdot n)=k \cdot D(n)\) 。输出答案对 \(10^9+7\) 。
\(Hint\)
对于满足条件的 \(10^l \le n \le 10^r\) 的数字，符合 \(sum_r-sum_l\) 。
题解
对于条件 \(D(k \cdot n)=k \cdot D(n)\) ，如果各位数字上的数 乘以 \(k\) 小于 \(10\) 即可。所以每一位可以取的数字数量是 \(t=9/k+1\) 。
\(sum_i\) 则为 \(t^i\) 个。所以答案即为 \(t^{r}-t^{l}\) 个。别忘了快速幂取模！
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define umap unordered_map
#define endl '\n'
using namespace std;
using i128 = __int128;
const int mod =1e9+7;
template <typename T>void read(T&x){x=0;int f = 1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
}
template <typename T>void print(T x) {if (x < 0) { putchar('-'); x = -x; }if (x > 9) print(x / 10);putchar(x % 10 + '0');
}
#define int long long
long long qpow(long long a,long long b,long long p=mod)
{long long res = 1 ;while (b){if (b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;
}
const int N=500005;
const int M=2000005;
inline void solve()
{int l,r,k;cin>>l>>r>>k;int t=9/k+1;cout<<(qpow(t,r)-qpow(t,l)+mod)%mod<<endl;
}signed main()
{ios;int T=1;cin>>T;for(;T--;) solve();return 0;
}