# CFR 51 D. Beautiful numbers ( Digit DP )

Problem - D - Codeforces

T ≤ 10
1 ≤ L, R ≤ 9e18

dp[ i ][ j ][ k ][ l ]: 考慮前 i 位，模 lcm( 1, 2, .. 9 ) 為何，已出現的數位的集合，是否嚴格小於 x，滿足這些條件的數量。

O3 + avx2 優化壓線通過。

O( 20 * lcm( 1, 2, .. 9 ) * 50 )

#pragma GCC optimize ("O3")
#pragma GCC target ("avx2") // ターゲットの変更 sse4, avx, avx2 など

#include <bits/stdc++.h>
using namespace std;

int mp[ 2520 + 1 ];
int rmp[ 48 ];

long long dp[ 2 ][ 2520 ][ 48 ][ 2 ];

int lcm( int a, int b ) {
if( not a or not b ) return a ? a : b;
return a / __gcd( a, b ) * b;
}

long long solve( long long x ) { // [ 1, x ]
vector< int > vec;
for( long long i = x; i; i /= 10 ) {
vec.emplace_back( i % 10 );
}
reverse( vec.begin(), vec.end() );
memset( dp[ 0 ], 0, sizeof( dp[ 0 ] ) );
dp[ 0 ][ 0 ][ 0 ][ 0 ] = 1;
for( int i = 0; i < vec.size(); ++i ) {
memset( dp[ ~i & 1 ], 0, sizeof( dp[ ~i & 1 ] ) );
for( int j = 0; j < 2520; ++j ) {
for( int k = 0; k < 48; ++k ) {
for( int l = 0; l < 2; ++l ) {
long long c = dp[ i & 1 ][ j ][ k ][ l ];
if( not c ) continue;
int lim = l ? 9 : vec[ i ];
for( int d = 0; d <= lim; ++d ) {
dp[ ~i & 1 ][ ( j * 10 + d ) % 2520 ][ mp[ lcm( rmp[ k ], d ) ] ][ l or d < lim ] += c;
}
}
}
}
}
long long res = 0;
for( int i = 0; i < 2520; ++i ) {
for( int j = 0; j < 48; ++j ) {
for( int k = 0; k < 2; ++k ) {
if( i % rmp[ j ] == 0 ) {
res += dp[ vec.size() & 1 ][ i ][ j ][ k ];
}
}
}
}
return res;
}

signed main() {
ios::sync_with_stdio( 0 );
set< int > bag;
for( int s = 1; s < 1 << 9; ++s ) {
int l = 1;
for( int i = 0; i < 9; ++i ) {
if( s >> i & 1 ) {
l = lcm( l, i + 1 );
}
}
bag.emplace( l );
}
for( auto it = bag.begin(); it != bag.end(); ++it ) {
static int __ptr = 0;
mp[ *it ] = __ptr;
rmp[ __ptr ] = *it;
++__ptr;
}
int T;
cin >> T;
for( int ti = 0; ti < T; ++ti ) {
long long L, R;
cin >> L >> R;
cout << solve( R ) - solve( L - 1 ) << endl;
}
return 0;
}