傳送門
題意:
思路:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll a[100010],b[100010],num[100010];
ll cnt,pri[100010],mu[100010],vis[100010];
ll res[100010];
void oula()
{
for(int i = 2; i <= 100000; i++)
{
if(!vis[i])pri[++cnt] = i,mu[i] = -1;
for(int j = 1; j <= cnt && pri[j]*i <= 100000; j++)
{
vis[pri[j]*i] = 1;
if(i%pri[j] == 0)break;
mu[pri[j]*i] = -mu[i];
}
}
}
int main()
{
mu[1] = 1;
oula();
int n;
cin>>n;
ll ans = 0;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= n; i++)cin>>b[i];
for(int i = 1; i <= n; i++)
{
int f = mu[i];
for(int j = i; j <= n; j+=i)num[a[b[j]]]++;
for(int j = i; j <= n; j+=i)ans += num[b[a[j]]]*f;
for(int j = i; j <= n; j+=i)num[a[b[j]]] = 0;
}
cout<<ans<<endl;
}