Codeforces Beta Round #51 D. Beautiful numbers(数位dp)

时间:2024-09-22 00:05:44

题目链接:https://codeforces.com/contest/55/problem/D

题目大意:给你一段区间[l,r],要求这段区间中可以整除自己每一位(除0意外)上的数字的整数个数,例如15,因为15既可以整除1也可以整除5,所以15符合要求。
(1 ≤ li ≤ ri ≤ 9 ·1018).
Examples
input
Copy
1
1 9
output
Copy
9
input
Copy
1
12 15
output
Copy
2

解题思路:很明显的数位dp,首先我们可以想一个数要整除它的每一位除0意外,那我们可以转化成可以整除它的每一位的最小公倍数即可。而我们可以直接求出1-9的最小公倍数为2520,取模不改变它们间的倍数关系,因为数很大所以我们每次可以对2520取模就可以了。所以我们可以很容易想到定义一个数组dp[20][2525][2525],dp[pos][mul][sta]表示的是第搜索到第pos位数值为mul(模2520后)每一位的最小公倍数为sta的合法数的个数,但我们发现这样状态数很多是会超时的,所以我们必须想办法进行优化,我们认真想想发现比2520小的数中并不是每一个数都有可能是1-9中某些数字的倍数,我们把2520中可能是1-9某些数字的倍数的数筛出来就好了,发现只有48个,我们把dp数组改为dp【20】【2525】【50】,这样就不会超时了,相当于做了一个离散化处理。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int a[],k[];
ll l,r,dp[][][];
ll dfs(int pos,int mul,int sta,int limit){
if(pos==) return mul%sta==;
if(!limit&&dp[pos][mul][k[sta]]!=-)
return dp[pos][mul][k[sta]];
int up=limit?a[pos]:;
ll ans=;
for(int i=;i<=up;i++){
if(i==){ //当该位为0时,不求最小公倍数
ans+=dfs(pos-,mul*%,sta,limit&&i==a[pos]);
}else{
int tmp=lcm(sta,i);
ans+=dfs(pos-,(mul*+i)%,tmp,limit&&i==a[pos]);
}
}
if(!limit&&dp[pos][mul][k[sta]]==-)
dp[pos][mul][k[sta]]=ans;
return ans;
}
ll solve(ll x){
int pos=;
while(x){
a[++pos]=x%;
x/=;
}
return dfs(pos,,,);
}
int main(){
memset(dp,-,sizeof(dp));
int t,cnt=;
cin>>t;
for(int i=;i<=;i++){
if(%i==)k[i]=++cnt; //2520%i不为0表示i一定不是1-9中某些数字的最小公倍数
}
while(t--){
cin>>l>>r;
cout<<solve(r)-solve(l-)<<endl;
}
return ;
}