[Solution][数论-GCD计数]BZOJ1101,2045,2301

【一个经典问题】

求满足数对个数。

【暴力?】

,极限数据下显然超时滚粗。

【转化】

转化为.

不过为什么这样是合理的呢?

可以表示中是的倍数的个数,可以表示中是的倍数的个数。那么两者相乘就可以表示数对中满足的倍数的数对个数。

本来这些数对都应该被减去的,不过他们之中是存在着交集的。

从而我们考虑容斥原理。

的情况显然应该是加上的,我们就从这个大整体向下减。

再假设是质数的情况,暂且将它们都减去。

否则当不含平方因子的时候,当有偶数个不同质数因子的时候,被减了偶数遍,应该加上;否则应该减去。

含平方因子的时候,实验发现他之前已经被减过正好遍,不必处理。

因而我们发现对于每个,的系数就是的莫比乌斯函数!

于是可以用欧拉筛预处理出莫比乌斯函数,再在内扫一遍即可!

【优化】

打表发现是呈块状分布的,因此只需预处理莫比乌斯函数的前缀和,就可以在的时间内计算得出结果。

对于多组询问,这个优化是必不可少的。

【Problems】

BZOJ2045

模板题。

【代码】

#include<cstdio>
#include<cstring>
#define N (1000000)
inline int min(int a , int b)
{
    return a < b ? a : b;
}
typedef long long LL;
int prime[N + 10] , top , mobius[N + 10];
bool notprime[N + 10];
LL getans(int x , int y)
{
    LL res = 0;
    int lim = min(x , y);
    for(int i = 1 , now = 0 ; i <= lim ; i = now + 1)
    {
        now=min(x/(x/i),y/(y/i));
        res+=(LL)(mobius[now]-mobius[i-1])*(x/i)*(y/i);
    }
    return res;
}
int main()
{
    register int i , j;
    int A , B , t;
    scanf("%d%d%d" , &A , &B , &t);
    mobius[1] = 1;
    int lim = min(A / t , B / t);
    for(i = 2 ; i <= lim ; ++i)
    {
        if (!notprime[i])
        {
            prime[top++] = i;
            mobius[i] = -1;
        }
        for(j = 0 ; j < top ; ++j)
        {
            if (i * prime[j] > lim)
                break;
            notprime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                mobius[i * prime[j]] = 0;
                break;
            }
            else
                mobius[i * prime[j]] = -mobius[i];
        }
    }
    for(i = 2 ; i <= lim ; ++i)
        mobius[i] += mobius[i - 1];
    printf("%lld" , getans(A/t , B/t));
    return 0;
}

BZOJ1101

又一道模板题。

【代码】

#include<cstdio>
#include<cstring>
#include<cctype>
#define N (50000)
inline int min(int a , int b)
{
    return a < b ? a : b;
}
inline char getc()
{
    static const int L = 1 << 15;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint()
{
    static char c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
int prime[N + 10] , top , mobius[N + 10];
bool notprime[N + 10];
void pre()
{
    int i , j;
    mobius[1] = 1;
    for(i = 2 ; i <= N ; ++i)
    {
        if (!notprime[i])
        {
            mobius[i] = -1;
            prime[top++] = i;
        }
        for(j = 0 ; j < top ; ++j)
        {
            if (i * prime[j] > N)
                break;
            notprime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                mobius[i * prime[j]] = 0;
                break;
            }
            else
                mobius[i * prime[j]] = -mobius[i];
        }
    }
    for(i = 2 ; i <= N ; ++i)
        mobius[i] += mobius[i - 1];
}
int get(int x , int y)
{
    int lim = min(x , y);
    int res = 0;
    for(int i = 1 , now = 0 ; i <= lim ; i = now + 1)
    {
        now=min(x/(x/i),y/(y/i));
        res+=(mobius[now]-mobius[i-1])*(x/i)*(y/i);
    }
    return res;
}
void answer()
{
    int A , B , t;
    A = getint();
    B = getint();
    t = getint();
    printf("%d\n" , get(A/t,B/t));
}
int main()
{
    pre();
    int T = getint();
    while(T--)
        answer();
    return 0;
}

BZOJ2301

只比之前多了一步转化。。不多说了。

【代码】

#include<cstdio>
#include<cstring>
#include<cctype>
#define N (50000)
inline char getc()
{
    static const int L = 1 << 15;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
     
    return *S++;
}
inline int getint()
{
    static char c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
inline int min(int a , int b)
{
    return a < b ? a : b;
}
int prime[N + 10] , top , mobius[N + 10];
bool notprime[N + 10];
void pre()
{
    int i , j;
    mobius[1] = 1;
    for(i = 2 ; i <= N ; ++i)
    {
        if (!notprime[i])
        {
            prime[top++] = i;
            mobius[i] = -1;
        }
        for(j = 0 ; j < top ; ++j)
        {
            if (i * prime[j] > N)
                break;
            notprime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                mobius[i * prime[j]] = 0;
                break;
            }
            else
                mobius[i * prime[j]] = -mobius[i];
        }
    }
    for(i = 1 ; i <= N ; ++i)
        mobius[i] += mobius[i - 1];
}
int get(int x ,int y)
{
    int res = 0;
    int lim = min(x , y);
    for(int i = 1 , now = 0 ; i <= lim ; i = now + 1)
    {
        now = min(x/(x/i),y/(y/i));
        res += (mobius[now]-mobius[i-1])*(x/i)*(y/i);
    }
    return res;
}
void ask()
{
    int a , b , c , d , p;
    a = getint();
    b = getint();
    c = getint();
    d = getint();
    p = getint();
    int res = get(b/p,d/p)-get(b/p,(c-1)/p)-get((a-1)/p,d/p)+get((a-1)/p,(c-1)/p);
    printf("%d\n" , res);
}
int main()
{
    pre();
    int T = getint();
    while(T--)
        ask();
    return 0;
}
comments powered by Disqus