题解 | #莫反做法#

这种问题直接上莫比乌斯反演即可，不怎么费大脑直接统计

设函数

显然我们的答案就是

由莫比乌斯反演得：

显然很好求，代码如下

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

int tr[N], n;
int u[N], primes[N], st[N], cnt;

int lowbit(int x) {
	return x & -x;
}

void add(int x, int v) {
	for(int i = x; i < N; i += lowbit(i))
		tr[i] += v;
}

int query(int x) {
	int res = 0;
	for(int i = x; i; i -= lowbit(i))
		res += tr[i];
	return res;
}

// 线性筛法，求莫比乌斯函数
void init(int n)
{
    u[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            u[i] = -1;
        }
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                u[t] = 0;
                break;
            }
            u[t] = u[i] * -1;
        }
    }

    //for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + u[i];
}


void solve() {
    cin >> n;
    vector<int> a(n), pos(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i], pos[a[i]] = i;

   	init(n);

    LL res = 0;
   	for(int d = 1; d <= n; d ++ ) if(u[d]) {
   		vector<int> arr;
   		for(int i = d; i <= n; i += d) arr.pb({pos[i]});
   		sort(arr.begin(), arr.end());
   		int all = 0;
   		for(auto i : arr) {
   			res += (all - query(a[i])) * u[d];
   			add(a[i], 1);
   			all ++ ;
   		}

   		for(auto i : arr) add(a[i], -1);
   	}

   cout << res;
}

int main() { 
    int T = 1;
    //cin >> T;
    while(T -- ) {
        solve();
    }
    return 0;
}