[ABC254D] Together Square Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$，求满足以下条件的二元组 $(i,j)$$(i, j)$ 数量：$1\le i,j\le n,i\times j=k^2(k\in {\mathbb{N}}^{\ast })$$1 \le i, j \le n, i \times j = k^2(k \in \mathbb{N}^*)$。

Solution

首先有一个较为显然的想法，即埃筛 $[1,n]$$[1, n]$ 每个数的所有因数，然后枚举每个 $i^2,i\in [1,n]$$i^2, i \in [1, n]$，将 $i\times i$$i \times i$ 转化为 $(i\times t)\times ({\displaystyle \frac{i}{t}})$$(i \times t) \times (\dfrac{i}{t})$，其中 $t$$t$ 为 $i$$i$ 的因数，然后如果 $i\times t\le n$$i \times t \le n$ 那么若 $t=1$$t = 1$ 则 $ans\leftarrow ans+1$$ans \leftarrow ans + 1$，反之 $ans\leftarrow ans+2$$ans \leftarrow ans + 2$。不过很遗憾这个很简单也很好写的思路是假的，不难发现比如 $6\times 6\Rightarrow 4\times 9$$6 \times 6 \Rightarrow 4 \times 9$，这里的因数是 ${\displaystyle \frac{3}{2}}$$\dfrac{3}{2}$，然后我们忽略了，所以会漏。

考虑正解，有个妙妙转化，即将原式的 $i,j$$i, j$ 转化为 $i=a^2\times c,j=b^2\times c$$i = a^2 \times c, j = b^2 \times c$，然后我们钦定 $i<j$$i \lt j$，此时计算后对于每个答案都 $\times 2$$\times 2$ 可以不漏 $i>j$$i \gt j$ 的部分，然后将最后的答案加上 $n$$n$ 即不漏 $i=j$$i = j$ 的部分。

然后考虑处理钦定 $i<j$$i \lt j$ 后的答案，不难想到有 $i<j<n\Rightarrow a^2\times c<b^2\times c<n\Rightarrow a^2<b^2<{\displaystyle \frac{n}{c}}\Rightarrow a<b<\sqrt{{\displaystyle \frac{n}{c}}}$$i \lt j \lt n \Rightarrow a^2 \times c \lt b^2 \times c \lt n \Rightarrow a^2 \lt b^2 \lt \dfrac{n}{c} \Rightarrow a \lt b \lt \sqrt{\dfrac{n}{c}}$。

于是不难发现 $a,b$$a, b$ 都是 $\sqrt{n}$$\sqrt{n}$ 级别的，于是枚举 $a,b$$a, b$，对于确定的 $a,b$$a, b$，则显然有 $c\in [1,{\displaystyle \frac{n}{b^2}}]$$c \in [1, \dfrac{n}{b^2}]$，则此时的答案贡献即为 $2\times \lfloor {\displaystyle \frac{n}{b^2}}\rfloor$$2 \times \lfloor \dfrac{n}{b^2} \rfloor$。然后发现这个东西还是假的，会重，即对于 $gcd(a,b)\ne 1$$\gcd(a, b) \neq 1$ 的 $c$$c$，显然会被 $a^{\prime }={\displaystyle \frac{a}{gcd(a,b)}},b^{\prime }={\displaystyle \frac{b}{gcd(a,b)}}$$a' = \dfrac{a}{\gcd(a, b)}, b' = \dfrac{b}{\gcd(a, b)}$ 所包含，所以不难想到只要将对答案的贡献转化为 $2\times \lfloor {\displaystyle \frac{n}{b^2}}\rfloor \times [gcd(a,b)=1]$$2 \times \lfloor \dfrac{n}{b^2} \rfloor \times [\gcd(a, b) = 1]$ 即可不重不漏地求出答案。

Code

xxxxxxxxxx
53
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
ll ans(0);
27

28
int main(){
29
    N = read();
30
    for(int a = 1; a * a <= N; ++a)
31
        for(int b = a + 1; b * b <= N; ++b)
32
            if(__gcd(a, b) == 1)
33
                ans += 2 * (N / (b * b));
34
    printf("%lld\n", ans + N);
35
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
36
    return 0;
37
}
38

39
template < typename T >
40
inline T read(void){
41
    T ret(0);
42
    int flag(1);
43
    char c = getchar();
44
    while(c != '-' && !isdigit(c))c = getchar();
45
    if(c == '-')flag = -1, c = getchar();
46
    while(isdigit(c)){
47
        ret *= 10;
48
        ret += int(c - '0');
49
        c = getchar();
50
    }
51
    ret *= flag;
52
    return ret;
53
}

UPD

update-2022_12_06 初稿