【BZOJ3309】DZY Loves Math

Description

对于正整数\(n\)，定义\(f(n)\)为\(n\)所含质因子的最大幂指数。例如\(f(1960)=f(2^3×5^1×7^2)=3\),\(f(10007)=1\),\(f(1)=0\)。

给定正整数\(a,b\)，求\(\sum\limits_{a_i=1}\sum\limits_{b_j=1}f(\gcd(i,j))\)。

Input

第一行一个数\(T\)，表示询问数。

接下来\(T\)行，每行两个数\(a,b\)，表示一个询问。

Output

对于每一个询问，输出一行一个非负整数作为回答。

HINT

\(T≤10000\)

\(1≤a,b≤10^7\)

推式子可以得到

设\(g(T)=\sum_{d|T}f(d)\mu(\frac{T}{d})\)，想一下卷积发现没啥用，然后我就放弃了。

浪费了一次打表的大好机会...打表可以发现\(g\)只有\(01\)两种值，但是没什么显然的性质，于是我们可以暴力按意义分类讨论取\(0\)或者\(1\)

然后我们讨论一下，设\(p\)代表质数

• \(g(p)=1\)

• 然后在计算式中令\(\frac{T}{d}\)的幂全为\(0\)或\(1\)，这样\(\mu\)才能产生贡献。

  这样的话可以发现\(f(d)\)只有两种取值\(f(T)\)与\(f(T-1)\)，暴力讨论这两种取值。

  可以得到式子\(g(T)=-\sum_{d|x\&\&f(d)\not=f(x)}\mu(\frac{x}{d})\)

  然后继续讨论可能取的\(01\)情况，发现如果幂全相等，可以取\((-1)^{k+1}\)，\(k\)为约数个数

  否则就取\(0\)

  线筛的时候维护一下最小质因子的幂数和最小质因子的幂

Code:

#include <cstdio>

#include <algorithm>

#define ll long long

const int N=1e7;

using std::min;

int pri[N+10],ispri[N+10],a[N+10],b[N+10],cnt;

ll f[N+10],ans,n,m;

void init()

{

    for(int i=2;i<=N;i++)

    {

        if(!ispri[i])

        {

            b[i]=pri[++cnt]=i;

            f[i]=a[i]=1;

        }

        for(int j=1;j<=cnt&&i*pri[j]<=N;j++)

        {

            ispri[i*pri[j]]=1;

            if(i%pri[j]==0)

            {

                a[i*pri[j]]=a[i]+1;

                b[i*pri[j]]=b[i]*pri[j];

                if(i==b[i]) f[i*pri[j]]=1;

                else f[i*pri[j]]=a[i/b[i]]==a[i]+1?-f[i/b[i]]:0;

                break;

            }

            else

            {

                a[i*pri[j]]=1,b[i*pri[j]]=pri[j];

                f[i*pri[j]]=a[i]==1?-f[i]:0;

            }

        }

    }

    for(int i=1;i<=N;i++) f[i]+=f[i-1];

}

int main()

{

    init();int T;scanf("%d",&T);

    while(T--)

    {

        ans=0;

        scanf("%lld%lld",&n,&m);

        for(ll l=1,r;l<=min(n,m);l=r+1)

        {

            r=min(n/(n/l),(m/(m/l)));

            ans+=(n/l)*(m/l)*(f[r]-f[l-1]);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

2018.12.15