P2257 YY的GCD_牛客博客

按照套路化到最后是：

$Ans = \sum \limits_{T = 1}^ n \lfloor \frac n T \rfloor ^2 \sum \limits _{p | T} \mu(\frac T p) [P$ $is$ $Prime].$

问题就在于怎么求 $f(T) =\sum \limits _{p | T} \mu(\frac T p) [P$ $is$ $Prime].$

法 $1$ :

对 $T$ 做唯一分解，则

$f(T) = \begin{cases} k(-1)^{k - 1} , T = p_1p_2...p_k \\ (-1)^{k - 1},T = p_1p_2...p_i^2...p_{k - 1}p_k\\ 0, else \end{cases}$

然后用数组记录 $n$ 含有的质数个数，是否为以上两种形式之一，即可递推。

法 $2$ :

考虑在线性筛的时候处理。

$case 1 :$ $f(p) = 1.$

$case 2 :$ 筛合数时， $p_j|i$ ，

若 $i$ 的唯一分解中每一项的幂次都为 $1$ ，则只有 $p = p_j$ 时 $\mu(\frac {ip_j} p) \not= 0$ ， $f(ip_j) = \mu(i)$ .

若 $i$ 的唯一分解中每一项的幂次不都为 $1$ ，则有一项的幂次不小于 $2$ ，则 $f(ip_j) = 0 = \mu(i).$

故 $f(ip_j) = 0 = \mu(i).$

$case 3 :$ 筛合数时， $p_j\not| i$ ，

由法 $1$ , $f(ip_j) = \mu(i) - f(i).$

法 $1$ 代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i ++)
#define dwn(i,a,b) for(int i = (a); i >= (b); i --)
using namespace std;
const int maxn = 1e7 + 100;

int cut, p[maxn], isp[maxn], can1[maxn], can2[maxn];
ll cntp[maxn], g[maxn];
void gt(int n)
{
    if(can1[n])
        g[n] = cntp[n] * ((cntp[n] - 1) % 2 == 1? -1LL: 1LL);
    if(can2[n])
        g[n] = (cntp[n] % 2 == 1? -1LL: 1LL);
}
void shai()
{
    int n = 1e7;
    g[1] = 0;
    cntp[1] = 0;
    can1[1] = 1;
    can2[1] = 0;
    rep(i,2,n)
    {
        if(!isp[i])
        {
            p[ ++ cut] = i;
            cntp[i] = 1;
            can1[i] = 1;
            can2[i] = 0;
            gt(i);
        }
        for(int j = 1; j <= cut && i * p[j] <= n; j ++)
        {
            isp[i * p[j]] = 1;
            if(i % p[j] == 0)
            {
                cntp[i * p[j]] = cntp[i];
                can1[i * p[j]] = 0;
                if(can1[i] == 1)
                    can2[i * p[j]] = 1;
                else
                    can2[i * p[j]] = 0;
                gt(i * p[j]);
                break;
            }
            else
            {
                cntp[i * p[j]] = cntp[i] + 1;
                can1[i * p[j]] = can1[i];
                can2[i * p[j]] = can2[i];
                gt(i * p[j]);
            }
        }
    }
    rep(i, 2, n) g[i] = g[i] + g[i - 1];
}
int main()
{
    shai();
    int T;
    cin >> T;
    rep(ci,1,T)
    {
        int n, m;
        cin >> n >> m;
        ll Ans = 0;
        for(int l = 1; l <= n && l <= m;)
        {
            int r = min(n / (n / l), m / (m / l));
            Ans += (ll)(n / l) * (ll)(m / l) * (g[r] - g[l - 1]);
            l = r + 1;
        }
        cout << Ans << endl;
    }
    return 0;
}