CodeForces1985G 题解思路

userId_undefined

沈思邈

秩序白银

2025-02-12 12:10:43

发布于：上海

4阅读
0回复
0点赞

思路

D(k⋅n)=k⋅D(n)D(k\cdot n)=k\cdot D(n)

所以n⋅kn\cdot k不进位

最高位：9k\dfrac{9}{k}种

其他位：(9k+1)(\dfrac{9}{k}+1)种

对于10m≤n<10m+110^m\leq n<10^{m+1}

共有9k(9k+1)i\dfrac{9}{k}(\dfrac{9}{k}+1)^i种

所以对于10l≤n<10r10^l\leq n<10^r

共有9k⋅∑i=ln=r−1(9k+1)i\dfrac{9}{k}\cdot \sum_{i=l}^{n=r-1} (\dfrac{9} {k}+1)^i种

令S=∑i=ln=r−1(9k+1)iS=\sum_{i=l}^{n=r-1} (\dfrac{9}{k}+1)^i

则9k⋅S=∑i=l+1n=r(9k+1)i\dfrac{9}{k}\cdot S=\sum_{i=l+1}^{n=r} (\dfrac{9} {k}+1)^i

9k⋅S−S=(9k+1)r−(9k+1)l\dfrac{9}{k}\cdot S-S=(\dfrac{9}{k}+1)^r-(\dfrac{9}{k}+1)^l

(9k−1)S=(9k+1)r−(9k+1)l(\dfrac{9}{k}-1)S=(\dfrac{9}{k}+1)^r-(\dfrac{9}{k}+1)^l

S=(9k+1)r−(9k+1)l9k−1S=\dfrac{(\dfrac{9}{k}+1)^r-(\dfrac{9}{k}+1)^l}{\dfrac{9} {k}-1}

共有9k⋅S\dfrac{9}{k}\cdot S种

AC CODE

#include<iostream>
using namespace std;
#define int unsigned long long
const int MOD=1e9+7;
int t,L,R,k;
int fast_pow(int x,int n){
	int s=1;
	for(;n;n>>=1,x=(x*x)%MOD)if(n&1)s=(s*x)%MOD;
	return s;
}
signed main(){
	cin>>t;
	while(t--){
		cin>>L>>R>>k;
		int p=9/k;
		int angs=(((fast_pow(p+1,R-L)-1)%MOD)+MOD)%MOD;
		angs=((fast_pow(p+1,L)%MOD)*angs)%MOD;
		cout<<angs<<"\n";
	}
	return 0;
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论