神秘的消 题。
题目链接。
题意
给定一个长为 的排列 ，求 且 的 对数。
。
题解
考虑令 ，并使用
。
那么 相当于 。
注意到此时 与 互质，且 与 互质，所以上述条件相当于 且 。
考虑忽略
的条件，先求出所有满足的 ，再去掉 的情况。
维护数组 表示所有
中，满足 且 的 的数量。
那么可以发现，对于一个
来说，合法的 的数量便是 。
（自己思考一下 且
的条件就能明白这为什么是对的。）
考虑这样做的时间复杂度，首先
是一个
的数组，显然开不下，所以需要使用 map 维护。
再来计算处理
数组的复杂度，可以发现最坏需要在 map 中插入 次，所以这部分复杂度是 的。
查询的复杂度完全相同，这样就得到了一个 的做法，可以通过 G1。
核心代码大概长这个样子（其中
存储所有 的因数）：
1
2
| for(int i=1;i<=n;i++) for(int j:d[y[i]]) vis[x[i]][j]++;
for(int i=1;i<=n;i++) for(int j:d[y[i]]) ans+=vis[j][x[i]];
|
如果要优化这个做法，必须要去掉一个 ，考虑避免使用 map 来消掉一个 。
想想我们为什么要用 map，原因是 的数组开不下。
但是一个
的数组是开的下的，那么我们枚举一个 ，考虑能否计算所有 的贡献。
维护 是容易的，找到所有
的 ，像上面一样插入即可。
查询也是容易的，发现
只会给所有 的 产生贡献，那么我们直接枚举 就可以了。
特别地，这里我们可以先枚举
再枚举 ，这样这里的枚举总复杂度是
的。
所以我们得到了一个复杂度是 的做法。非常神奇。
代码
上述做法并没有保证 ，所以需要先把 的情况去掉。
容易发现 的情况只会在 时恰好被计算一次（这个条件与
等价），减掉之后就只剩 的情况了，显然 与 的方案数相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
vc<int>num1[500001];
vc<int>num2[500001];
int val[500001];
vc<int>d[500001];
int a[500001];
int n;
int main()
{
for(int i=1;i<=500000;i++) for(int j=1;i*j<=500000;j++) d[i*j].push_back(i);
int T=read();
while(T--)
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
ll ans=0;
for(int i=1;i<=n;i++)
{
int x=i,y=a[i],g=__gcd(x,y);
x/=g,y/=g;
num1[x].push_back(y);
num2[y].push_back(x);
if(y%x==0) ans--;
}
for(int x=1;x<=n;x++)
{
for(int j:num1[x]) for(int k:d[j]) val[k]++;
for(int y=x;y<=n;y+=x) for(int k:num2[y]) ans+=val[k];
for(int j:num1[x]) for(int k:d[j]) val[k]--;
}
for(int i=1;i<=n;i++) num1[i].clear(),num2[i].clear();
printf("%lld\n",ans/2);
}
return 0;
}
|
感谢观看！