需要优化一波常数。
以及刚才那个版本是错的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 10005 using namespace std; int t1=0,t2=0; long long ans=0,cnt=0,num[maxn],s[maxn],l,r; bool vis[maxn]; void get_baka(int bit,long long nums) { if (nums>r) return; if (nums) num[++t1]=nums; get_baka(bit+1,nums*10+6); get_baka(bit+1,nums*10+8); } long long gcd(long long a,long long b) { if (!b) return a; return gcd(b,a%b); } void dfs(int now,long long nums,int val) { if (now>t2) { if (nums!=1) { if (val&1) ans+=r/nums-(l-1)/nums; else ans-=r/nums-(l-1)/nums; } return; } dfs(now+1,nums,val); long long aft=nums/gcd(num[now],nums); if ((double)num[now]*aft<=r) dfs(now+1,num[now]*aft,val+1); } int main() { scanf("%lld%lld",&l,&r); get_baka(0,0); sort(num+1,num+t1+1); for (register int i=1;i<=t1;i++) { if (vis[i]) continue; s[++t2]=num[i]; for (register int j=i+1;j<=t1;j++) { if (!(num[j]%num[i])) vis[j]=true; } } for (register int i=1;i<=t2;i++) num[i]=s[t2-i+1]; dfs(1,1,0); printf("%lld ",ans); return 0; }