Given a positive integers nn , Mobius function \mu(n)μ(n) is defined as follows:
\displaystyle \mu(n) = \begin{cases} 1 &n = 1 \\ (-1)^k & n = p_1p_2\cdots p_k \\ 0 &other \end{cases}μ(n)=??????1(−1)k0?n=1n=p1?p2??pk?other?
p_i (i = 1, 2, \cdots, k)pi?(i=1,2,?,k) are different prime numbers.
Given two integers mm, nn, please calculate \sum_{i = 1}^{m} \mu(in)∑i=1m?μ(in).
One line includes two integers m (1 \le m \le 2e9)m(1≤m≤2e9), n (1 \le n \le 1e12)n(1≤n≤1e12) .
One line includes the answer .
2 2
-1
SOLUTION:
怎么感觉徐州喜欢出递归的题呢。。。一场比赛有三个题是往下递归的
n==1的时候杜教筛就完了
原文：https://www.cnblogs.com/DeaphetS/p/9614591.html
CODE:
#include<bits/stdc++.h>
using namespace std;
#define N 10000001
#define LL long long
LL n,m,cnt,p[N],f[N],s[N];
map<LL,LL>M;
bool x[N];
void pretype()
{
f[1]=1;
for(int i=2;i<N;i++)
{
if(!x[i])p[++cnt]=i,f[i]=-1;
for(int j=1;j<=cnt && i*p[j]<N;j++)
{
f[i*p[j]]=-f[i];
x[i*p[j]]=true;
if(i%p[j]==0){f[i*p[j]]=0;break;}
}
}
for(int i=1;i<N;i++)
s[i]=s[i-1]+f[i];
}
LL get(LL n)
{
if(n<N)return f[n];
LL k=1;
for(LL i=2;i*i<=n;i++)
if(n%i==0)
{
if(n%(i*i)==0)return 0;
k*=-1,n/=i;
}
if(n>1)k*=-1;return k;
}
LL get_M(LL n)
{
if(n<N)return s[n];
if(M[n])return M[n];
LL res=1,nxt;
for(LL i=2;i<=n;i=nxt+1)
{
nxt=n/(n/i);
res-=(nxt-i+1)*get_M(n/i);
}
return M[n]=res;
}
LL F(LL n,LL m)
{
if(n==1)return get_M(m);
LL miu=get(n),res=0;
if(miu==0)return 0;
for(LL d=1;d*d<=n && d<=m;d++)if(n%d==0)
{
res+=get(d)*F(d,m/d);
if(d*d!=n&&n/d<=m)res+=get(n/d)*F(n/d,m/(n/d));
}
return miu*res;
}
int main()
{
pretype();
scanf("%lld%lld",&m,&n);
printf("%lld\n",F(n,m));
}
【2018徐州网络赛】Easy Math (推柿子 + 递归 + 杜教筛）
原文：https://www.cnblogs.com/zhangbuang/p/11200426.html