[POI2007 Zap]容斥原理

【url】http://www.zybbs.org/JudgeOnline/problem.php?id=1101

【题目大意】没法大意了- -，直接原题吧。

【算法】

直接暴力容斥可以在O(min(a,b))时间复杂度内解决一个询问。

先a/=d,b/=d

答案为Sum(d[i]*(a/i)*(b/i))，2<=i<=a其中d[i]是容斥系数。

那么可知a/i只有sqrt(a)级别种结果。b/i也只有sqrt(b)级别种结果。

也就是说随着i的递增，a/i和b/i总的变化数是sqrt(a)+sqrt(b)级别的。

于是对于a/i和b/i相同的放一组。一共只会有sqrt(a)+sqrt(b)级别组。通过对d构建前缀和数组可以做到O(1)处理每一组。

然后就没了。

【其它】

作为AC的门徒、外加NOI2010囧人，此题不切说不过去- –

【CODE】

#include

#include

const int N=50005;

int d[N];

int S[N];

bool prime[N];

 

void predo(){

    memset(prime,true,sizeof(prime));

    for (int i=2;i<=50000;i++) d[i]=1;

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

        if (prime[i]){

            for (int j=i+i;j<=50000;j+=i){

                prime[j]=false;

                if (j/i%i==0) d[j]=0;

                d[j]=-d[j];

            }

            d[i]=-1;

        }

    S[1]=0;

    for (int i=2;i<=50000;i++) S[i]=S[i-1]+d[i];

}

 

void swap(int &x,int &y){

    int t=x;

    x=y;

    y=t;

}

 

int min(int x,int y){return x

 

int Get_Next(int a,int b){  // let ret=a/b this function get the smallest number x satisfy a/x!=ret && x>b

    return a/(a/b)+1;

}

 

int main(){

    predo();

    int Tc;

    scanf("%d",&Tc);

    while (Tc–){

        int m,n,dd;

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

        m/=dd;

        n/=dd;

        long long ans=(long long)m*n;

        if (m>n) swap(m,n);

        for (int i=2;i<=m;){

            int Next=min(Get_Next(m,i),Get_Next(n,i));

            long long tmp=(long long)(m/i)*(n/i);

            ans+=(S[Next-1]-S[i-1])*tmp;

            i=Next;

        }

        printf("%lldn",ans);       

    }

}