天天看點

序列。。。

​​傳送門​​

序列。。。

題意:

思路:

#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;
}      

繼續閱讀