牛客 14648 序列 ( 莫比乌斯 )

题意：

思路： gcd(x, y) = 1 想到莫比乌斯

　　　牛客 14648 序列 ( 莫比乌斯 )

　　然后我们枚举 i，然后枚举 j 是 i 的倍数，那gcd(i, j) = i

　　　然后对这些数，枚举有多少满足第二个条件的，然后最后累加答案即可。

#include <bits/stdc++.h>
#define LL long long
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF INT_MAX
#define inf LLONG_MAX
#define PI acos(-1)
using namespace std;

const int N = 1e6 + 5;

int a[N], b[N];

int mu[N], vis[N], pre[N], tot = 0;
LL c[N], res[N];
void init(int n) { ///初始化莫比乌斯函数
    mu[1] = 1;
    rep(i, 2, n) {
        if(!vis[i]) pre[++tot] = i, mu[i] = -1;
        rep(j, 1, tot) {
            if(i * pre[j] > n) break;
            vis[i * pre[j]] = 1;
            if(i % pre[j] == 0) {
                mu[i * pre[j]] = 0;break;
            }
            else mu[i * pre[j]] = -mu[i];
        }
    }
}

void solve() {
    int n; scanf("%d", &n);
    init(n);
    rep(i, 1, n) scanf("%d", &a[i]);
    rep(i, 1, n) scanf("%d", &b[i]);
    rep(i, 1, n) { /// 枚举 i 
        for(int j = i; j <= n; j += i) c[a[b[j]]]++; /// 枚举 i 的倍数
        for(int j = i; j <= n; j += i) res[i] += c[b[a[j]]]; /// 累加答案
        for(int j = i; j <= n; j += i) c[a[b[j]]]--; /// 消除影响
    }
    LL ans = 0;
    rep(i, 1, n) ans += res[i] * mu[i];
    printf("%lld
", ans);
}

int main() {

    solve();

    return 0;

}

牛客 14648 序列 ( 莫比乌斯 )

相关推荐