over 4 years ago

bzoj2820:http://blog.csdn.net/jayye1994/article/details/12621589 讲的实在是好,但是看得不仔细所以有些地方花了很多时间,特此标注
http://ydcydcy1.blog.163.com/blog/static/216089040201355104013804/ g(x) h(x) F(x)那里还要理解一下
http://hi.baidu.com/liouzhou_101/item/44b1ab1289a25c19d0d66df5 感觉上和上一个有些相似?
bzoj1101:http://hi.baidu.com/lydrainbowcat/item/cc363be5a342fbf32b09a4b9 分块方面,miu的容斥原理

Mobius反演

有两种形式:
设 F(n) = sigma( f(d) ), 其中d | n (也就是n%d==0) 。则 f(n) = sigma( F(d)mu(n/d) )
设 F(d) = sigma( f(n) ),其中d | n 。则f(d) = sigma( F(n)*mu(n/d) )。
1 (x = 1)
其中mu(x) = (-1)^k (x含有k个不同素因子且每个素因子有且仅有一个)
0 (其他情况)
其实
Mobius反演就是偏序集上的容斥原理,mu函数就是容斥系数*。

bzoj2820&&SPOJ-PGCD Primes in GCD Table

题意:
给你a,b,求gcd(i, j) = k (k为素数)的个数,1 <= i <= a, 1 <= j <= b。
解题思路:
要求gcd(i, j) = k,设F(x)为gcd(i, j)为x的倍数的个数,f(x)为gcd(i,j)为x的个数。则F(x) = (a/x)(b/x)
根据公式可以得到 f(k) = sigma( F(n)
mu(n/k)),其中k | n,n <= a && n <= b。

假如我只需要求一个gcd(i, j) = k的个数,可以对于a,b都除k,则转化成求gcd(i, j) = 1 (1 <= i <= a , 1<= j <= b)。
则答案即为f(1) = sigma( F(x)mu(x) ) ( x <= min(a, b) ),然后可以求出mu函数,1~min(a,b)枚举得到答案
这样的复杂度为O(n)的,有点高,F(x) = (a/x)
(b/x),很容易可以看出F(x)是递减的且为若干段值相等的段,即有些连续部分值都相等,所以可以分段处理,这样子的复杂度是O( sqrt(n) )的。

好,现在求单独gcd(i ,j) = k的已经可以处理了,不过题目要求k是所有的素数,很显然不能枚举所有的素数。
重新观察下上面的式子 f(k) = sigma( F(n)mu(n/k) ),对于所有的f(k)都加起来为
**sigma( F(n) ( mu(n/k1) + mu(n/k2) +mu(n/k3) +... ) )
*其中n >= 2,ki为不大于n的素因子。
设cnt(n) = F(n) * ( mu(n/k1) + mu(n/k2) +mu(n/k3) +... )

对于mu( n/k1 )如果这个值为0的话就可以忽略了。所以可以枚举所有mu(x)不为0的数,然后 cnt(x * k) += mu(x),就可以处理出所有的cnt(n),然后用上面的分段的方法就可以解决了。
PAY ATTENTION:分段处理那里需要注意一下,还想了想T_T

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#define maxn 10000001

using namespace std;
int miu[maxn],p[maxn],sum[maxn];
bool can[maxn];
long long ans;
int t,m,n,pn=0;
void prepare(int tot)
{
    int i,j; 
    memset(can,true,sizeof(can));
    miu[1]=1;
    for (i=2;i<=tot;i++)
    {
        if (can[i]) miu[i]=-1,p[++pn]=i;
        for (j=1;j<=pn&&i*p[j]<=tot;j++)
        {    can[i*p[j]]=false;
            if (i%p[j]==0) {miu[i*p[j]]=0;break;}
            miu[i*p[j]]=-miu[i];
        }
    }
    for (i=1;i<=pn;i++)
      for (j=1;j*p[i]<=tot;j++)
        sum[j*p[i]]+=miu[j];
    for (i=1;i<=tot;i++) sum[i]+=sum[i-1];
}
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0')result=result*10+c-'0',c=getchar();
    return result*bj;
}
int main()
{
    int i,a,b,border;
    prepare(maxn-1);
    t=readln();
    while (t--)
    {
        ans=0;
        n=readln();m=readln();
        for (i=1;i<=min(n,m);i++)
        {
            a=n/i;b=m/i;
            border=min(n/a,m/b);
            ans+=a*1ll*b*(sum[border]-sum[i-1]);
            i=border;
        }
        printf("%lld\n",ans);
    }
}

bzoj1101&&poi2007

题意:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d
sol:这是上一题的简化版,只需要求gcd(x/d,y/d)=1 ----->gcd(x,y)=1(x<=a/d,y<=b/d)
同样进行mobius反演,答案就为sigma(miu(k)(n/d/k)(m/d/k)) k<=n/d && k<=m/d
wrong:1、统计前缀和出现错误
2、注意在赋值给long long之前会不会爆int

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#define maxn 50001

using namespace std;
int miu[maxn],sum[maxn],p[maxn];
bool can[maxn];
int n,m,t,d,pn=0;long long ans=0;
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0'))c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0')result=result*10+c-'0',c=getchar();
    return result*bj;
}
void makemiu(int tot)
{   int i,j;
    memset(can,true,sizeof(can));
    miu[1]=1;
    for (i=2;i<=tot;i++)
    {
        if (can[i]) miu[i]=-1,p[++pn]=i;
        for (j=1;j<=pn&&i*p[j]<=tot;j++)
        { can[i*p[j]]=false;
          if (i%p[j]==0) {miu[i*p[j]]=0;break;}
          miu[i*p[j]]=-miu[i];
        }
    }
    for (i=1;i<=tot;i++) sum[i]=miu[i]+sum[i-1];
}
int main()
{
    int i,a,b,border;
    makemiu(50000);
    t=readln();
    while (t--)
    {
        n=readln();m=readln();d=readln();
        n=n/d;m=m/d;ans=0;
        if (n>m) swap(n,m);
        for (i=1;i<=n;i++)
        {
            a=n/i;b=m/i;
            border=min(n/a,m/b);
            ans+=1ll*a*b*(sum[border]-sum[i-1]);
            i=border;
        }
        printf("%lld\n",ans);
    }
}

bzoj2301&&haoi2011

题意:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。
sol:在上一题的基础上容斥
wrong:1、看清题目再做,一开始没看到下面的等号,注释的部分是(a,b) (c,d) 的情况
2、在longlong之前赋值会爆啊啊啊啊啊

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#define maxn 50000

using namespace std;
int p[maxn],miu[maxn],sum[maxn];
bool can[maxn];
long long result=0;int pn=0;
inline int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0'))c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0')result=result*10+c-'0',c=getchar();
    return result*bj;
}
inline void makemiu(int tot)
{
    int i,j;
    memset(can,true,sizeof(can));
    miu[1]=1;
    for (i=2;i<=tot;i++){ 
        if (can[i]) p[++pn]=i,miu[i]=-1;
        for (j=1;j<=pn&&p[j]*i<=tot;j++)
        {
            can[i*p[j]]=false;
            if (i%p[j]==0) {miu[i*p[j]]=0;break;}
            miu[i*p[j]]=-miu[i];
        }
    }
    for (i=1;i<=tot;i++) sum[i]=sum[i-1]+miu[i];
}
inline long long work(int n,int m,int d)
{
    n/=d;m/=d;
    if (n==0||m==0) return 0;
    if (n>m) swap(n,m);
    long long ans=0;int i,border,a,b;
    for (i=1;i<=n;i++)
    {
        a=n/i;b=m/i;
        border=min(n/a,m/b);
        ans+=1ll*a*b*(sum[border]-sum[i-1]);
        i=border;
    }
    return ans;
}
int main()
{
    int t=readln(),a,b,c,d,k;
    makemiu(50000);
    while (t--)
    {
        a=readln();b=readln();c=readln();d=readln();k=readln();
        //if (b-a<=1|d-c<=1) {printf("0\n");continue;}
        //result=work(b-1,d-1,k)-work(a,d-1,k)-work(b-1,c,k)+work(a,c,k);
        result=work(b,d,k)-work(a-1,d,k)-work(b,c-1,k)+work(a-1,c-1,k);
        printf("%lld\n",result);
    }
}
← 点分治 【poj1741&&bzoj1499】 【bzoj1005】【HAOI2008】【prufer编码】【排列组合】明明的烦恼 →
 
comments powered by Disqus