就是爆搜嘛。
先从大到小排个序能减去dfs树上很大的一部分。这个技巧要掌握。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100500
using namespace std;
long long l,r,num[maxn],s[maxn],t1=,t2=,t,ans=;
bool vis[maxn];
void get_baka(long long bit,long long nums)
{
if ((bit>t) || (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);
}
long long lcm(long long a,long long b)
{
return a*b/gcd(a,b);
}
void dfs(long long now,long long num,long long val)
{
if (now==t2+)
{
if (num!=) ans+=((r/num)-((l-)/num))*val;
return;
}
dfs(now+,num,val);
long long aft=lcm(num,s[now]);
if (aft<=r) dfs(now+,aft,val*(-));
}
int main()
{
scanf("%lld%lld",&l,&r);
t=(long long)(log(r)/log())+;
get_baka(,);
sort(num+,num+t1+);
for (long long i=;i<=t1;i++)
{
if (vis[i]) continue;
s[++t2]=num[i];
for (long long j=i+;j<=t1;j++)
{
if (!num[j]%num[i])
vis[j]=true;
}
}
for (int i=;i<=t2;i++) num[i]=s[t2-i+];
for (int i=;i<=t2;i++) s[i]=num[i];
dfs(,,-);
printf("%lld\n",ans);
return ;
}