P2257 YY的GCD

· · 个人记录

P2257 YY的GCD

题意描述：

求 \displaystyle\sum_{i=1}^{n}\sum_{j=1}^{m} [gcd(i,j) \in prime], T\leq 10^4, n,m\leq 10^7

solution：

反演进阶题。

先枚举一下 p 可得：

\displaystyle\sum_{p\in prime}\sum_{i=1}^{n}\sum_{j=1}^{m} [gcd(i,j) == p]

由 \displaystyle\sum_{d\mid n} \mu(d) =\begin{cases} 1 & n = 1 \\ 0 & other \\\end{cases} 可得：

\displaystyle\sum_{p\in prime}\sum_{i=1}^{n}\sum_{j=1}^{m} \sum_{d\mid i,d\mid j} \mu(d)

先枚举一下 d 可得：

\displaystyle\sum_{p\in prime}\sum_{d=1}^{n\over d} \mu(d) \sum_{i=1}^{n\over d}\sum_{j=1}^{m\over d} [gcd(i,j) == 1] =\displaystyle\sum_{p\in prime}\sum_{d=1}^{n\over d}\mu(d) {n\over dp} {m\over dp} $\displaystyle\sum_{Q=1}^{n} {n\over Q} {m\over Q}\sum_{p\mid Q,p\in prime} \mu({Q\over p})

然后我们就可以直接把 \displaystyle F(Q) = \sum_{p\mid Q,p\in prime} \mu({Q\over p})，给求出来。

考虑枚举每个质因数 p ,那么 p 只会对他的倍数有贡献。这样的复杂度就降为 O(nlnn) 的了。

剩下的部分整除分块即可。

总的时间复杂度为 O(T\sqrt(n) + nlnn) (大力吸氧就过了)

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e7+10;
int T,n,m,tot;
int prime[N],mu[N],ans[N];
bool check[N];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
void YYCH()
{
    mu[1] = 1;
    for(int i = 2; i <= N-5; i++)
    {
        if(!check[i])
        {
            prime[++tot] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
        {
            check[i * prime[j]] = 1;
            if(i % prime[j] == 0)
            {
                mu[i * prime[j]] = 0;
                break;
            }
            else mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= tot; i++)
    {
        for(int j = 1; j * prime[i] <= N-5; j++)
        {
            ans[j * prime[i]] += mu[j];
        }
    }
    for(int i = 1; i <= N-5; i++) ans[i] = ans[i-1] + ans[i];
}
int calc(int n,int m)
{
    int res = 0;
    if(n > m) swap(n,m);
    for(int l = 1, r; l <= n && l <= m; l = r+1)
    {
        r = min(n/(n/l),m/(m/l));
        res += (ans[r] - ans[l-1]) * (n/l) * (m/l);
    }
    return res;
}
signed main()
{
    T = read(); YYCH();
    while(T--)
    {
        n = read(); m = read();
        printf("%lld\n",calc(n,m));
    }
    return 0;
}

其实这道题还可以做到 O(T\sqrt(n) + n) 的。

最后一步 dp 化 Q 的时候，可以变为： \displaystyle\sum_{Q=1}^{n} {n\over Q}{m\over Q} \sum_{d\mid Q} \mu(d) isp({Q\over d})

后面那个 \displaystyle F(Q) = \sum_{d\mid Q} \mu(d) isp({Q\over d}) 是可以线性筛的。

设 i = p_1p_2p_3...., 只有当 {Q\over d} = p1,p2,p3... 时，isp({Q\over d}) 才成立。

1.当 Q 为质数的时候,显然 F(Q) = 1

2.当 Q = 1 时，显然 F(Q) = 0

3.当 i % prime[j] == 0 的时候： F(i * prime[j]) = \mu(i)

证明：

此时 prime[j] 为 i 的最小质因子 p_1 。

F (i) = \mu({i \over p_1}) + \mu({i\over p_2}) + ....\mu({i\over p_n}) F(i * p_1) = \mu({i * p_1 \over p_1}) + \mu({i * p_1 \over p_2}) + ....\mu({i * p1\over p_n})

显然 i * p_1 分解质因数后， p_1 的次数是大于等于 2 的，所以除了 \mu({i * p_1\over p1} ) 之外，其他都为零。

因为 p1 的次数大于等于 2，\mu({i*p1\over p_n}) = 0 。

所以 F(i * p1) = \mu(i).

4.当 i % prime[j] != 0 时： F(i * prime[j]) = mu[i]-F(i)

证明：

此时 prime[j] 为 i 的最小质因子 p_0 。

F (i) = \mu({i \over p_1}) + \mu({i\over p_2}) + ....\mu({i\over p_n}) F(i * p_0) = \mu({i * p_0\over p_0}) + \mu({i * p_0 \over p_1}) + \mu({i * p_0 \over p_2}) + ....\mu({i * p0\over p_n})

显然有 \mu({i*p_0\over p_1}) = -\mu({i\over p_1}) 。假设 {i\over p_1} = x ,他分解后质因数为 x = p_1p_2...p_n

综上： $F(i * p_0) = \mu({i * p_0\over p_0}) + \mu({i * p_0 \over p_1}) + \mu({i * p_0 \over p_2}) + ....\mu({i * p0\over p_n})

​ = \mu(i) -\mu({i\over p_1}) -\mu({i\over p_2}) .....-\mu({i\over p_n})

​ = \mu(i) - F(i)

然后就可以直接线性筛了。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e7+10;
int T,n,m,tot;
int prime[N],mu[N],ans[N];
bool check[N];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
void YYCH()
{
    mu[1] = 1; ans[1] = 0;
    for(int i = 2; i <= N-5; i++)
    {
        if(!check[i])
        {
            prime[++tot] = i;
            mu[i] = -1;
            ans[i] = 1;
        }
        for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
        {
            check[i * prime[j]] = 1;
            if(i % prime[j] == 0)
            {
                mu[i * prime[j]] = 0;
                ans[i * prime[j]] = mu[i];
                break;
            }
            else 
            {
                mu[i * prime[j]] = -mu[i];
                ans[i * prime[j]] = mu[i] - ans[i];
            }
        }
    }
    for(int i = 1; i <= N-5; i++) ans[i] = ans[i-1] + ans[i];
}
int calc(int n,int m)
{
    int res = 0;
    if(n > m) swap(n,m);
    for(int l = 1, r; l <= n && l <= m; l = r+1)
    {
        r = min(n/(n/l),m/(m/l));
        res += (ans[r] - ans[l-1]) * (n/l) * (m/l);
    }
    return res;
}
signed main()
{
    T = read(); YYCH();
    while(T--)
    {
        n = read(); m = read();
        printf("%lld\n",calc(n,m));
    }
    return 0;
}