题意:求[l,r]中高位%低位等于0的数字个数。(不含0)
分析:此题有三种方法。
1.暴搜,毕竟最多才10个位。
2.数位dp,预处理好整体的,再处理细节。
dp[i][j]表示第i位上的数字位j的情况数,dp[i][j]+=dp[i-1][k](j%k==0)
3.猜想这样的数字并不多,于是打表。
数位dp
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>#define LL long longusing namespace std;int dp[][];
int a[];
void init(){
for(int i=;i<;i++) dp[][i]=;
for(int i=;i<;i++){
for(int j=;j<;j++){
for(int k=;k<;k++){
if(j%k==) dp[i][j]+=dp[i-][k];
}
}
}
}int solve(int x){
int len=;
int ans=;
while(x){
a[++len]=x%;
x/=;
}
for(int i=;i<len;i++){///先加上len-1位的情况
for(int j=;j<;j++)
ans+=dp[i][j];
}
for(int i=;i<a[len];i++) ans+=dp[len][i]; ///len位,且小于最高位数字的情况 for(int i=len-;i>=;i--){///已最高位的数字为基准,寻找符合条件的,再加上
for(int j=a[i]-;j>;j--){
if(a[i+]%j==) ans+=dp[i][j];
}
if(!a[i]) break;
if(a[i+]<a[i] || a[i+]%a[i]!=) break;
}
return ans;
}int main(){
init();
int t;
cin>>t;
while(t--){
int l,r;
cin>>l>>r;
cout<<solve(r+)-solve(l)<<endl;
}
return ;
}
打表
#include<iostream>//离线处理
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#define INF 0x0f0f0f0f
using namespace std;
int a[] = {
,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,
,,,,,,,,,,,,,,
,,,,,,,,,,,,,,
,,,,,,,,,,,,,,
,,,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,
};
int main()
{
int t;
cin >> t;
cout << a[] << endl;
while (t--)
{
int ans = ;
int l, r;
scanf("%d%d", &l, &r);
for (int i = ; i < ; i++)
{
if (a[i] >= l && a[i] <= r) ans++;
}
cout << ans << endl;
}
return ;
}