Codeforces-55D Beautiful numbers

http://codeforces.com/problemset/problem/55/D

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.

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).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

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).

 

题意:求区间美丽数的个数。所谓美丽数,是指一个数可以被它的每一位数字整除。

思路:因为num可以被它的每一位整除,等价于num可以被其每一位的lcm整除。

但是,状态不能设为(第pos位,以前每位的lcm),举个例子,num1=32,num2=312,假如按刚刚的状态跑到最后'2'那一位时,当前lcm都是3,但是312%6==0,而32%6!=0。

即算是不是美丽数,必须由整个num%lcm(每一位)。

由于x%b==x%(k*b)%b,lcm(1~9)=2520,num%lcm=num%2520%lcm

状态设为(第pos位,以前数%2520的值,当前lcm)

但是这个状态有18*2525*2520,空间开不下,因为1~9任意组合的lcm是离散的,只有48种组合,最后一维可以离散化一下。

参考这篇https://blog.csdn.net/qq_33184171/article/details/52332586

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long

ll T,A,B;
ll a[20],dp[20][2600][50];
ll lcm_id[2530];

ll Lcm(ll a,ll b)
{
	if(!b)return a;
	return a/__gcd(a,b)*b;
}

ll dfs(ll pos,ll mod,ll lcm,bool limit)
{
	if(pos==-1)return mod%lcm==0;
	if(!limit&&dp[pos][mod][lcm_id[lcm]]!=-1)return dp[pos][mod][lcm_id[lcm]];
	int up= (limit?a[pos]:9);
	ll ans=0;
	for(int i=0;i<=up;i++)
	{
		ans+=dfs(pos-1,(mod*10+i)%2520,Lcm(lcm,i),limit&&i==a[pos]);
	}
	if(!limit)dp[pos][mod][lcm_id[lcm]]=ans;
	return ans;
}

ll solve(ll n)
{
	int pos=0;
	while(n)
	{
		a[pos++]=n%10;
		n/=10;
	}
	return dfs(pos-1,0,1,1);
}

void init()
{
	int idx=0;
	bool vis[2530]={0};
	for(int i=1;i<(1<<9);i++)
	{
		int ret=1;
		for(int j=0;j<9;j++)if((1<<j)&i)ret=Lcm(ret,j+1);
		if(!vis[ret])
		{
			vis[ret]=1;
			lcm_id[ret]=++idx;
		}
	}
}

int main()
{
//	freopen("input.in","r",stdin);
	memset(dp,-1,sizeof(dp));
	init();
	cin>>T;
	while(T--)
	{
		cin>>A>>B;
		cout<<solve(B)-solve(A-1)<<endl;
	}
	return 0;
} 

 

全部评论

相关推荐

当初高考报计算机真是造大孽了啊!卷的飞起!哪都是计算机的人,考研,考公,找工作全他奶的计算机的人,太难了。国企也是。关键一届比一届卷,造大孽了!
_Lyrics_:因为计算机,没有体验到快乐的大学研究生时光,好不容易修完课程就要出去实习,看着别人专业可以一起搓麻将,游山玩水,而我却要自己一个人住在北上不到十平米的出租屋,每天两点一线
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务