Codeforces 55D Beautiful Number，codeforces55d
Codeforces 55D Beautiful Number
a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits.
Input
The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9 ·1018).
Output
Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).
Sample test(s)
Input
1
1 9
Output
9
Input
1
12 15
Output
2
思路:
代碼思路參考了:
AC_Von
![]()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)= 0;i < (n);i++)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
typedef long long ll;
const int MOD = 2520;
ll dp[21][2520][50];
int d[21],index[MOD+5];
void init()
{
for(int i = 1,tot = 0;i <= MOD;i++)
if(MOD % i == 0) index[i] = tot++;
MS1(dp);
}
int lcm(int a,int b)
{
return a/__gcd(a,b)*b;
}
ll dfs(int pos,int prev,int prelcm,int edge)
{
if(pos == -1) return prev % prelcm?0:1; // ***
ll ans = dp[pos][prev][index[prelcm]];
if( !edge && ~ans) return ans;
ans = 0;
int e = edge ? d[pos]:9;
for(int i = 0;i <= e;i++){
int nowlcm = i ? lcm(prelcm,i) : prelcm;
int nowv = (prev * 10 + i)%MOD;
ans += dfs(pos - 1,nowv,nowlcm,edge && i == e);
}
if(!edge) dp[pos][prev][index[prelcm]] = ans;
return ans;
}
ll query(ll n)
{
MS0(d);int tot = 0;
while(n){
d[tot++] = n%10;
n /= 10;
}
return dfs(tot - 1,0,1,1);
}
int main()
{
init();
int T;
cin>>T;
while(T--){
ll l,r;
scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",query(r) - query(l-1));
}
}
View Code
