推公式。f[n]=1-∑f[n/i](i=2...n)。然后递归+记忆化搜索。yyl说这叫杜教筛？时间复杂度貌似是O（n 2/3）的？
#include#include #include #include using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define ll long long#define qwq(x) for(edge *o=head[x];o;o=o->next)const int mod=1e6+7;const int nmax=7e6+5;struct edge{ int to,dis;edge *next;};edge es[mod],*pt=es,*head[nmax];int mo[nmax+1],pe[nmax];bool vis[nmax+1];void add(int u,int v,int d){ pt->to=v;pt->dis=d;pt->next=head[u];head[u]=pt++;}int get(ll n){ if(n<=nmax) return mo[n]; int tp=n%mod; qwq(tp) if(o->to==n) return o->dis; ll last,ans=0; for(ll i=2;i<=n;i=last+1){ last=n/(n/i); ans+=(last-i+1)*get(n/i); } add(tp,n,1-ans); return 1-ans;}int main(){ mo[1]=1;int cnt=0,tp; rep(i,2,nmax){ if(!vis[i]) pe[++cnt]=i,mo[i]=-1; rep(j,1,cnt){ tp=pe[j];if(tp*i>nmax) break;vis[i*tp]=1; if(i%tp==0){ mo[i*tp]=0;break; } mo[i*tp]=-mo[i]; } } rep(i,1,nmax) mo[i]+=mo[i-1]; ll n,m;scanf("%lld%lld",&n,&m); printf("%d\n",get(m)-get(n-1)); return 0;}
基准时间限制：3 秒 空间限制：131072 KB 分值: 320
收藏 
关注 莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下：
如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。
如果一个数不包含平方因子，并且有k个不同的质因子，那么miu(n) = (-1)^k。例如：miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。
给出一个区间[a,b]，S(a,b) = miu(a) + miu(a + 1) + ...... miu(b)。
例如：S(3, 10) = miu(3) + miu(4) + miu(5) + miu(6) + miu(7) + miu(8) + miu(9) + miu(10)
= -1 + 0 + -1 + 1 + -1 + 0 + 0 + 1 = -1。
Input
输入包括两个数a, b，中间用空格分隔(2 <= a <= b <= 10^10)
Output
输出S(a, b)。
Input示例
3 10
Output示例
-1