【2018徐州网络赛】Easy Math (推柿子 + 递归 + 杜教筛）

Given a positive integers nn , Mobius function mu(n)μ(n) is defined as follows:

 

displaystyle mu(n) = egin{cases} 1 &n = 1 \ (-1)^k & n = p_1p_2cdots 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).

Input

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) .

Output

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
",F(n,m));
}