ACM-ICPC 2018 서주 경기 지역 네트워크 예선 D. Easy Math(귀속식 + 두교 체)

Given a positive integers nnn , Mobius function μ ( n )\mu(n) μ(n) is defined as follows:
μ ( n ) = { 1 n = 1 ( − 1 ) k n = p 1 p 2 ⋯ p k 0 o t h e r\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 , ⋯ , k ) p i ( i = 1 , 2 , ⋯   , k ) pi(i=1,2,⋯,k)p_i (i = 1, 2,\cdots, k) pi(i=1,2,⋯,k)pi​(i=1,2,⋯,k)are different prime numbers.
Given two integers mmm, nnn, please calculate ∑ i = 1 m μ ( i n )\sum_{i = 1}^{m}\mu(in) ∑i=1m​μ(in) .
Input
One line includes two integers m(1≤m≤2e9)m (1\le m\le 2e9)m(1≤m≤2e9), n(1≤n≤1e12)n (1\le n\le 1e12)n(1≤n≤1e12) .
Output
One line includes the answer .
샘플 입력 복사 2
샘플 출력 복사-1

제목

n과 m를 구해 드리겠습니다.μ ( i n )\sum_{i=1}^m\mu(in) i=1∑m​μ(in)μ\mu μ모비우스 함수

생각

n이 제곱인자를 함유하고 있는 상황을 먼저 고려하면 각각의 i*n 다음에μ ( i n )\mu(in) μ(in) 모두 0이므로 n에 제곱인자가 함유되어 있지 않은 것을 고려해 n은 반드시 n=p1p2p3p4⋯pin=p_로 분해할 수 있다1p_2p_3p_4\cdots p_in=p1p2p3p4⋯pi 우리령 S(m, n)=∑i=1mμ ( i n ) S(m,n)=\sum_{i=1}^m\mu(in) S(m,n)=i=1∑m​μ(in) 그리고 지금 n n의 소인자 d d를 고려하면, d d는 n n의 임의의 소인자일 수 있다. 그러면 n d\frac {n} {d} dn과 d d의 상호작용이 틀림없다. 우리는 n을 분해하여 ∑i = 1m를 분해할 것이다μ ( i n ) = ∑ i = 1 m μ ( i ⋅ n d ⋅ d )\sum_{i=1}^m\mu(in)=\sum_{i=1}^m\mu\left ( i\cdot\frac{n}{d}\cdot d\right ) i=1∑m​μ(in)=i=1∑m​μ(i⋅dn⋅d) 그 중에서 dd와 nd\frac{n}{d}dn은 반드시 상호질이다. 그러면 나머지는 dd와 ii의 관계[1,m][1,m][1,m]의 수와 dd는 두 가지 상호질과 상호질만 있을 수 있다. 왜냐하면μ ( )\mu() μ() 적성 함수로서 ii와 dd의 상호작용이 있으면μ ( i ⋅ n d ⋅ d ) = μ ( i ⋅ n d ) μ ( d )\mu\left ( i\cdot\frac{n}{d}\cdot d\right )=\mu\left ( i\cdot\frac{n}{d}\right )\mu\left (d\right ) μ(i⋅dn​⋅d)=μ(i⋅dn​)μ(d) ∑ i = 1 m μ ( i ⋅ n d ⋅ d )\sum_{i=1}^m\mu\left ( i\cdot\frac{n}{d}\cdot d\right ) i=1∑m​μ(i⋅dn​⋅d) ∑ i = 1 m μ ( i ⋅ n d ) μ ( d ) = − ∑ i = 1 m μ ( i ⋅ n d )\sum_{i=1}^m\mu\left ( i\cdot\frac{n}{d}\right )\mu\left (d\right )=-\sum_{i=1}^m\mu\left ( i\cdot\frac{n}{d}\right ) i=1∑m​μ(i⋅dn​)μ(d)=−i=1∑m​μ(i⋅dn) 때문에μ ( d )\mu(d) μ(d) 단소수의 그의 값은 틀림없이 −1-1−1이다. 이 식과 원식의 관계를 생각하면 실제로 ii와 dd가 서로 질적이지 않은 부분을 하나 더 줄인 것을 발견할 수 있다. 그러면 우리는 그에게 ii와 dd가 서로 질적이지 않은 부분을 돌려주면 된다. 그러면 지금 [1,m][1,m][1,m]에서 소수 dd와 서로 질적이지 않은 수는 바로 그것이다. [1,m][1,m]에서 dd의 배수,1매에서 md\frac{m}{d}dm만 열거하면 됩니다. ∑i = 1mdμ ( i ⋅ d ⋅ n d ) = ∑ i = 1 m d μ ( i n )\sum_{i=1}^{\frac{m}{d}}\mu(i\cdot d\cdot\frac{n}{d})=\sum_{i=1}^{\frac{m}{d}}\mu(in) i=1∑dm​​μ(i⋅d⋅dn​)=i=1∑dm​​μ(in)이면 됐어, 요약하면 ∑i = 1mμ ( i n ) = − ∑ i = 1 m μ ( i ⋅ n d ) + ∑ i = 1 m d μ ( i n )\sum_{i=1}^m\mu(in)=-\sum_{i=1}^m\mu\left ( i\cdot\frac{n}{d}\right )+\sum_{i=1}^{\frac{m}{d}}\mu(in) i=1∑m​μ(in)=−i=1∑m​μ(i⋅dn​)+i=1∑dm​​μ(in) 즉 S(m, n) = −S(m, n d) + S(m d, n) S(m,\frac{n} {d}) + S(\frac{m} {d}, n) S(m, n) = −S(m, dn) + S(dm, n) = 이 귀속 방정식이 생겼습니다. 우리는 매번 현재의 n의 소인자 하나만 찾으면 귀속할 수 있습니다. 및 S(m, 1) S(0, n) = 0 및 S(m, 1) S(m, 1) = ∑i = 1 mμ ( i ) S(m,1)=\sum_{i=1}^m\mu(i) S(m,1)=i=1∑m​μ(i) m가 비교적 크기 때문에 우리는 두교 체로 모비우스 함수의 접두사와 두교 체로 구해야 한다. 두교 체는 O(n2 3) O(n^{\frac{2}{3}}) O(n32)에서 접두사와 이런 적성 함수의 n배(n은 비제곱인자수)를 구하는 것과 같은 형식을 구할 수 있다.)+∑i = 1 m d f(i n)\sum_{i=1}^mf(in)=f(d)\sum_{i=1}^mf\left ( i\cdot\frac{n}{d}\right )+\sum_{i=1}^{\frac{m}{d}}f(in) i=1∑m​f(in)=f(d)i=1∑m​f(i⋅dn​)+i=1∑dm​​f(in)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=10000000;
long long prime[1000000],num;
int vst[maxn+5],miu[maxn+5],mu_n;
inline void Pre()
{
    miu[1]=1;
    for (int i=2; i<=maxn; i++)
    {
        if (!vst[i]) prime[++num]=i,miu[i]=-1;
        for (int j=1; j<=num && (ll)i*prime[j]<=maxn; j++)
        {
            vst[i*prime[j]]=1;
            if (i%prime[j]==0)
            {
                miu[i*prime[j]]=0;
                break;
            }
            miu[i*prime[j]]=miu[i]*miu[prime[j]];
        }
    }
    for (int i=1; i<=maxn; i++) miu[i]+=miu[i-1];
}
unordered_map S;
inline int Sum(ll n)
{
    if (n<=maxn) return miu[n];
    if (S.find(n)!=S.end()) return S[n];
    int tem=1;
    ll l,r;
    for (l=2; l*l<=n; l++) tem-=Sum(n/l);
    for (ll t=n/l; l<=n; l=r+1,t--)
    {
        r=n/t;
        tem-=(r-l+1)*Sum(t);
    }
    return S[n]=tem;
}
long long f(long long m,long long n)
{
    if(m==0) return 0;
    if(n==1) return Sum(m);
    int flag=1;
    for(int i=1; prime[i]*prime[i]<=n; i++)
    {
        if(n%prime[i]==0)
        {
            flag=0;
            return -f(m,n/prime[i])+f(m/prime[i],n);
        }
    }
    if(flag)
    {
        return -f(m,n/n)+f(m/n,n);
    }
}
int judge(long long n)
{
    for(int i=1; prime[i]*prime[i]<=n; i++)
    {
        if(n%prime[i]==0)
        {
            int cnt=0;
            while(n%prime[i]==0)
            {
                n/=prime[i];
                cnt++;
            }
            if(cnt>=2)
            {
                return 0;
            }
        }
    }
    return 1;
}
int main()
{
    Pre();
    long long m,n;
    scanf("%lld%lld",&m,&n);
    if(!judge(n))
    {
        printf("0
");
        return 0;
    }
    long long ans=f(m,n);
    printf("%lld
",ans);
    return 0;
}