bzoj 2693: jzptab 线性筛积性函数

2693: jzptab

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 444 Solved: 174
[Submit][Status][Discuss]

Description

Input

一个正整数T表示数据组数

接下来T行每行两个正整数表示N、M

Output

T行每行一个整数表示第i组数据的结果

Sample Input

4 5

Sample Output

122

HINT
T <= 10000

N, M<=10000000

　　重新学习了一下积性函数方式推导莫比乌斯反演系列题目，感觉求sigma(gcd(x,y))、sigma(gcd(x,y)==1)用积性函数的性质推导应该还算是简单，但是求sigma(lcm(x,y))用积性函数就非常恶心了，具体推法详见jzp讲稿：

　传送门：http://wenku.baidu.com/link?url=_glgC9AsqkzOGXSe66vrbLWwf9mr_HZujxaAszME0pCbVtRdcTyhqODy801-tgQdoArjJYYwQGwpQ7E4mdA61OsRYO3qciEfusRQ51JPUCy

　　这道题是bzoj 2154《 Crash的数字表格》的多组询问版，如果我没记错的话，那道题我用的是O(n)求sigma(lcm(x,y))，但是jzp讲的神奇的方法可以O(n)预处理，O(sqrt(n))询问。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define MAXP 10010000

#define MAXN 10010000

#define MOD 100000009

typedef long long qword;

bool pflag[MAXP];

int prime[MAXP],topp=-;

int phi[MAXP];

int gg[MAXP];

qword gs[MAXP];

int mu[MAXP];

void init()

{

        phi[]=;

        gg[]=;

        mu[]=;

        for (int i=;i<MAXP;i++)

        {

                if (!pflag[i])

                {

                        prime[++topp]=i;

                        phi[i]=i-;

                        gg[i]=-i;

                        mu[i]=-;

                }

                for (int j=;j<=topp && i*prime[j]<MAXP;j++)

                {

                        pflag[i*prime[j]]=true;

                        if (i%prime[j]==)

                        {

                                phi[i*prime[j]]=phi[i]*prime[j];

                                gg[i*prime[j]]=gg[i];

                                mu[i*prime[j]]=;

                                break;

                        }

                        phi[i*prime[j]]=phi[i]*(prime[j]-);

                        gg[i*prime[j]]=gg[i]*(-prime[j]);

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

                }

        }

        for (int i=;i<MAXP;i++)

                gs[i]=(gs[i-]+(qword)gg[i]*i)%MOD;

        return ;

}

qword solve(int n,int m)

{

        qword res=;

        int l=;

        for (int i=;i<=min(n,m);i=l)

        {

                l=min(n/(n/i),m/(m/i))+;

                res=(res+((qword)(n/i)*(n/i+)/%MOD)%MOD*((qword)(m/i)*(m/i+)/%MOD)%MOD*(gs[l-]-gs[i-])%MOD)%MOD;

        }

        res=(res+MOD)%MOD;

        return res;

}

int main()

{

        freopen("input.txt","r",stdin);

        int n,m;

        int nn;

        init();

        scanf("%d",&nn);

        while (nn--)

        {

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

                printf("%lld\n",solve(n,m));

        }

}

秒客网