25分求调
查看原帖
25分求调
745332
Henry2012楼主2024/12/11 20:35
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=20;
bool st;
int f[N][32][21][15][15],a[N],pw2[32],pw3[21],pw5[15],pw7[15];
bool ed;
int dfs(int pos,int a2,int a3,int a5,int a7,bool lim,bool lead){
	if (a2<0 || a3<0 || a5<0 || a7<0) return 0;
	if (pos==0) return !(a2||a3||a5||a7||lead);
	if (!lim && !lead && f[pos][a2][a3][a5][a7]!=-1) return f[pos][a2][a3][a5][a7];
	int ans=0,up=lim ? a[pos] : 9;
	for (int i=0;i<=up;++i){
		if (i==0 && lead) ans+=dfs(pos-1,a2,a3,a5,a7,lim&&(i==up),lead&&(i==0));
		if (i==1) ans+=dfs(pos-1,a2,a3,a5,a7,lim&&(i==up),lead&&(i==0));
		if (i==2) ans+=dfs(pos-1,a2-1,a3,a5,a7,lim&&(i==up),lead&&(i==0));
		if (i==3) ans+=dfs(pos-1,a2,a3-1,a5,a7,lim&&(i==up),lead&&(i==0));
		if (i==4) ans+=dfs(pos-1,a2-2,a3,a5,a7,lim&&(i==up),lead&&(i==0));
		if (i==5) ans+=dfs(pos-1,a2,a3,a5-1,a7,lim&&(i==up),lead&&(i==0));
		if (i==6) ans+=dfs(pos-1,a2-1,a3-1,a5,a7,lim&&(i==up),lead&&(i==0));
		if (i==7) ans+=dfs(pos-1,a2,a3,a5,a7-1,lim&&(i==up),lead&&(i==0));
		if (i==8) ans+=dfs(pos-1,a2-3,a3,a5,a7,lim&&(i==up),lead&&(i==0));
		if (i==9) ans+=dfs(pos-1,a2,a3-2,a5,a7,lim&&(i==up),lead&&(i==0));
	}
	if (!lim && !lead) f[pos][a2][a3][a5][a7]=ans;
	return ans;
}
int calc(int n,int a2,int a3,int a5,int a7){
	int len=0;
	while (n) a[++len]=n%10,n/=10;
	return dfs(len,a2,a3,a5,a7,1,1);
}
signed main(){
	int l,r;
	scanf("%lld%lld",&l,&r);
	pw2[0]=pw3[0]=pw5[0]=pw7[0]=1;
	for (int i=1;;++i){
		pw2[i]=pw2[i-1]*2;
		if (pw2[i]>r) break;
	}
	for (int i=1;;++i){
		pw3[i]=pw3[i-1]*3;
		if (pw3[i]>r) break;
	}
	for (int i=1;;++i){
		pw5[i]=pw5[i-1]*5;
		if (pw5[i]>r) break;
	}
	for (int i=1;;++i){
		pw7[i]=pw7[i-1]*7;
		if (pw7[i]>r) break;
	}
	memset(f,-1,sizeof f);
	int m=sqrt(r),ans=0;
	for (int i=0;pw2[i]<=m;++i)
		for (int j=0;pw2[i]*pw3[j]<=m;++j)
			for (int k=0;pw2[i]*pw3[j]*pw5[k]<=m;++k)
				for (int p=0;pw2[i]*pw3[j]*pw5[k]*pw7[p]<=m;++p){
					int x=pw2[i]*pw3[j]*pw5[k]*pw7[p];  
					ans+=calc(r/x,i,j,k,p)-calc((l-1)/x,i,j,k,p);
				}
	printf("%lld",ans);
	return 0;
}

rt,是WA

2024/12/11 20:35
加载中...