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;
} 

 

全部评论

相关推荐

认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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