Article From:https://www.cnblogs.com/oi-forever/p/9125839.html

A given interval [L, R], to find the number of perfect numbers in the interval. (a number is a perfect number if and only if the number can be divided into non zero numbers on all its digits).

Conclusion: digits on digit only need to consider 2~9, so use a number.1<<8To indicate which numbers have appeared.
If a number is a multiple of all the digits, then it must be the multiple of its minimum common multiple, and all the minimum common multiplier is 2520, so the sum of the sum is directly to 2520.
dp[l][cnt][sum],lFor numeric length, what is the number of CNT digits, sum is the number sum.
dfs(int l,int cnt,int sum,bool sig),sigWhether it is a boundary or not.

 

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 2520;
#define int ll
ll dp[20][1 << 8][2520]; int t, dight[20], tot;

ll dfs(int l, int cnt, int sum, bool sig) {
	if(l == 0) {
		for (int i = 2; i <= 9; ++i) {
			if((cnt & (1 << (i - 2))) && (sum % i != 0)) return 0;
		} return 1;
	} 
	if(!sig && dp[l][cnt][sum] != -1) return dp[l][cnt][sum];
	int nex = (sig ?dight[l] :9); ll res = 0;
	for (int i = 0; i <= nex; ++i) {
		res += (i < 2) ?dfs(l - 1, cnt, (sum * 10 + i) % MOD, sig && (i == nex)) :dfs(l - 1, cnt | (1 << (i - 2)), (sum * 10 % MOD + i) % MOD, sig && (i == nex));
	}
	if(!sig) dp[l][cnt][sum] = res;
	return res;
}
ll calc(int a) {
	tot = 0;
	while(a) {
		dight[++tot] = a % 10; a /= 10;
	}
	return dfs(tot, 0, 0, true);
}
 main() {
	scanf("%lld", &t);
	memset(dp, -1, sizeof dp);
	while(t--) {
		ll l, r;
		scanf("%lld%lld", &l, &r);
		printf("%lld\n", calc(r) - calc(l - 1));
	}
	return 0;
}

 

  

 

Similar Posts:

Link of this Article: CF55D

Leave a Reply

Your email address will not be published. Required fields are marked *