文件详细信息

下载本文件

本文件的大小为 2588 字节。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int sz=4,p[sz]={2,3,5,7};
const int P=1000000007,maxcnt=8281,maxhash=37*25*13*13;
ll n;
int k,cnt;
struct Data{
	ll x;
	int a[sz];
}fac[10]={{0,0,0,0,0},{1,0,0,0,0},{2,1,0,0,0},{3,0,1,0,0},{4,2,0,0,0},{5,0,0,1,0},{6,1,1,0,0},{7,0,0,0,1},{8,3,0,0,0},{9,0,2,0,0}};
struct COM{
	Data num;
	int num_cnt;
}num[maxcnt];
bool operator<(const Data a,const Data b){
	return a.x<b.x;
}
bool operator<(const COM a,const COM b){
	return a.num_cnt>b.num_cnt;
}
Data operator*(const Data&a,const Data&b){
	Data ans;
	ans.x=a.x*b.x;
	for(int i=0;i<sz;i++)ans.a[i]=a.a[i]+b.a[i];
	return ans;
}
Data operator/(const Data&a,const Data&b){
	Data ans;
	ans.x=a.x/b.x;
	for(int i=0;i<sz;i++)ans.a[i]=a.a[i]-b.a[i];
	return ans;
}
int digit[13],len;
std::set<Data>s[14];
void init_dfs(int cur,int lim,int zero,Data now){
	if(s[cur].find(now)!=s[cur].end())return;
	s[cur].insert(now);
	if(cur==0)return;
	int d=lim?digit[cur-1]:9;
	if(zero)init_dfs(cur-1,lim&&d==0,1,now);
	for(int i=1;i<=d;i++)init_dfs(cur-1,lim&&i==d,0,now*fac[i]);
}
int f[13][maxhash];
int cnt_dfs(int cur,int lim,int zero,Data now){
	if(cur==-1)return now.x==1?1:0;
	int id=((now.a[0]*25+now.a[1])*13+now.a[2])*13+now.a[3];
	if(!lim&&!zero&&f[cur][id]!=-1)return f[cur][id];
	int ans=0,d=lim?digit[cur]:9;
	if(zero&&cur>0)ans+=cnt_dfs(cur-1,lim&&d==0,1,now);
	for(int i=1;i<=d;i++)
		if(now.x%i==0)
			ans+=cnt_dfs(cur-1,lim&&i==d,0,now/fac[i]);
	if(!lim&&!zero)f[cur][id]=ans;
	return ans;
}
struct Pos{
	ll val;
	int x,y;
};
bool operator<(const Pos a,const Pos b){
	return a.val<b.val;
}
std::priority_queue<Pos>q;
int main(){
	read(n),read(k);
	while(n){
		digit[len++]=n%10;
		n/=10;
	}
	init_dfs(len,1,1,Data{1,{0,0,0,0}});
	for(Data i:s[0])num[cnt++].num=i;
	memset(f,-1,sizeof(f));
	for(int i=0;i<cnt;i++)num[i].num_cnt=cnt_dfs(len-1,1,1,num[i].num);
	std::sort(num,num+cnt);
	for(int i=0;i<cnt;i++)q.push(Pos{(ll)num[i].num_cnt*num[0].num_cnt,i,0});
	ll ans=0;
	while(k--){
		if(q.empty())break;
		Pos u=q.top();
		q.pop();
		ans=(ans+u.val)%P;
		if(u.y<cnt-1)q.push(Pos{(ll)num[u.x].num_cnt*num[u.y+1].num_cnt,u.x,u.y+1});
	}
	write(ans),putchar('\n');
	return 0;
}