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