徐州赛区网络预赛 D Easy Math

比赛快结束的适合看了一下D题，发现跟前几天刚刚做过的HDU 5728 PowMod几乎一模一样，当时特兴奋，结果一直到比赛结束都一直WA。回来仔细一琢磨才发现，PowMod这道题保证了n不含平方因子，而Easy Math却没有。只要加一条特判，这道题就过了。

AC代码贴在下面。求莫比乌斯函数前缀和的那一部分是我当时在网上临时找的代码，向那位仁兄道谢。

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define ms(arr,a) memset(arr,a,sizeof arr)

#define debug(x) cout<<"< "#x" = "<<x<<" >"<<endl

typedef long long ll;

const int INF  = 0x3f3f3f3f;

const int Maxn = 1e7 * 2;

const int mod  = 2333333;

int pcnt = 0, prime[1300000]; // 质数

short  mu[Maxn];           //   莫比乌斯函数值

bool vis[Maxn];

void init() {

    mu[1] = 1;

    for (int i = 2; i < Maxn; i++) {

        if (vis[i] == 0) {

            mu[i] = -1;

            prime[++pcnt] = i;

        }

        for (int j = 1; j <= pcnt && i * prime[j] < Maxn; j++) {

            vis[i * prime[j]] = 1;

            if (i % prime[j] != 0)

                mu[i * prime[j]] = -mu[i];

            else {

                mu[i * prime[j]] = 0;

                break;

            }

        }

    }

    for (int i = 2; i < Maxn; i++) mu[i] += mu[i - 1];   //  函数前缀和

}

struct Hash {

    long long key;

    int value, next;

} node[mod];

int cnt = 0, Head[mod] = {0};

void Insert(long long N, int v) {  // 记忆

    int ha = N % mod;

    node[++cnt].key = N;

    node[cnt].value = v;

    node[cnt].next = Head[ha];

    Head[ha] = cnt;

}

int M(long long N) {

    if (N < Maxn) return mu[N];

    int ha = N % mod;

    for (int i = Head[ha]; i != 0; i = node[i].next) {

        if (node[i].key == N)   // 如果已经计算过

            {return node[i].value;}

    }

    int  ans = 0;

    for (long long i = 2, j; i <= N; i = j + 1) {

        j = N / (N / i);   // 分块加速

        ans += (j - i + 1) * M(N / i);

    }

    Insert(N, 1 - ans);  // 做记忆

    return 1 - ans;

}

ll n,m;

long long fac[30];int cntfac;

bool init_fac(ll x)

{

    cntfac=0;

    for(int i=1;prime[i]<sqrt(x);++i)

        if(x%prime[i]==0){fac[++cntfac]=prime[i];x/=prime[i];if(x%prime[i]==0)return false;}

    if(x>1)fac[++cntfac]=x;

    return true;

}

ll calc(ll n,ll m,int k)

{

    //debug(n);

    if(m==0)return 0;

    if(n==1)

    {

        if(m==0)return 0;

        else {return M(m);}

    }

    return -calc(n/fac[k],m,k-1)+calc(n,m/fac[k],k);

}

int main()

{

    //freopen("Input.txt","r",stdin);

    //freopen("1.txt","w",stdout);

    init();

    while(~scanf("%lld%lld",&m,&n))

    {

        if(init_fac(n))printf("%lld\n",calc(n,m,cntfac));

        else printf("0\n");

    }

    //freopen("CON","w",stdout);

    //system("start Output.txt");

}