C++(g++ 7.5.0) 解法, 执行用时: 139ms, 内存消耗: 544K, 提交时间: 2023-05-10 15:03:07

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
long long a,b,t,cnt,num[100000],c[100000],ans;
long long gcd(long long a,long long b)
{
	while (b)
	{
		long long c=a%b;
		a=b;
		b=c;
	}
	return a;
}
void solve(int k,long long s)
{
	if (abs(s)>b)	return;
	if (k>t)
	{
		if (abs(s)>1)	ans+=b/s-(a-1)/s;
		return;
	}
	solve(k+1,-s/gcd(abs(s),c[k])*c[k]);
	solve(k+1,s);
}
void dfs(long long s)
{
	if (s>b)	return;
	if (s>1)	num[++cnt]=s;
	dfs(s*10+6);
	dfs(s*10+8);
}
int main()
{
	cin>>a>>b;
	cnt=0;
	dfs(0);
	sort(num+1,num+cnt+1);
	t=0;
	for (int i=1;i<=cnt;++i)
	{
		bool flag=1;
		for (int j=1;j<i;++j)
			if (num[i]%num[j]==0)
				flag=0;
		if (flag)	c[++t]=num[i];
	}
	for (int i=t;i>=t/2;--i)
		swap(c[i],c[t-i+1]);
	ans=0;
	solve(1,-1);
	cout<<ans<<endl;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 85ms, 内存消耗: 444K, 提交时间: 2023-04-13 20:30:40

#include <bits/stdc++.h>
using namespace std;
long long s[10010],num[10010],a,b,ans = 0;
int cnt = -1,n = 0;
void dfs(long long p)
{
	if(p > b) return;
	num[++cnt] = p;
	dfs(p*10+6);
	dfs(p*10+8);
}
void get(int t,long long p,int u)
{
	ans += (b/p - (a-1)/p) * u;
	for(int i = t+1;i <= n;++i) 
		if(1.0*p/__gcd(p,s[i])*s[i] <= b)
			get(i,p/__gcd(p,s[i])*s[i],-u);	
}
int main()
{
	scanf("%lld%lld",&a,&b);
	dfs(0);
	sort(num+1,num+cnt+1);
	for(int i = 1;i <= cnt;++i)
	{
		if(!num[i]) continue; 
		for(int j = i+1;j <= cnt;++j)
			if(num[j] % num[i] == 0)	
				num[j] = 0;
	}
	for(int i = 1;i <= cnt;++i) 
		if(num[i])
			s[++n] = num[i];
	reverse(s + 1,s + n + 1);
	get(0,1,1);
	cout<<b - a + 1 - ans;		
	return 0;
}