传送门:【codeforces】55D. Beautiful numbers
题目分析:被每一位整除则用二进制记录已经包括的数字的个数,以及对2520取模后的状态。由于对5整除当且仅当最后一个数为0或5,对2整除当且仅当最后一个数为偶数,且1~9的最小公倍数为2520,不包括2,5后的最小公倍数为252,所以除最后一层对2520取模,其余时候都对252取模即可。由于整除的状态有限,最多只有48个,于是我们预处理出这48个数,并来一个映射就好(不然会TLE)。
通过这题我才知道dp只用一次清零即可。。。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define For( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define rev( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) LL L , R ; LL dp[19][252][48] ; int a[2521] , cnt ; int digit[19] ; int gcd ( int a , int b ) { return b ? gcd ( b , a % b ) : a ; } LL dfs ( int cur , int limit , int x , int y , LL ans = 0 ) { if ( cur < 0 ) return x % y == 0 ; if ( ~dp[cur][x][a[y]] && !limit ) return dp[cur][x][a[y]] ; int n = limit ? digit[cur] : 9 ; For ( i , 0 , n ) ans += dfs ( cur - 1 , limit && i == digit[cur] , cur ? ( x * 10 + i ) % 252 : ( x * 10 + i ) , i ? y * i / gcd ( y , i ) : y ) ; return limit ? ans : dp[cur][x][a[y]] = ans ; } LL solve ( LL n ) { int n1 = 0 ; while ( n ) { digit[n1 ++] = n % 10 ; n /= 10 ; } return dfs ( n1 - 1 , 1 , 0 , 1 ) ; } int main () { int T ; cnt = 0 ; For ( i , 1 , 2520 ) if ( 2520 % i == 0 ) a[i] = cnt ++ ; clr ( dp , -1 ) ; scanf ( "%d" , &T ) ; while ( T -- ) { scanf ( "%I64d%I64d" , &L , &R ) ; printf ( "%I64d\n" , solve ( R ) - solve ( L - 1 ) ) ; } return 0 ; }