C++14(g++5.4) 解法, 执行用时: 96ms, 内存消耗: 4872K, 提交时间: 2020-08-18 16:20:58

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin>>n;
    vector<ll> cnt(n+1),a(n+1),b(n+1),f(n+1);

    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=1; i<=n; i++)
        cin>>b[i];
    for(int i=n; i>=1; i--)
    {
        for(int j=i; j<=n; j+=i)
            cnt[a[b[j]]]++;
        for(int j=i; j<=n; j+=i)
            f[i] += cnt[b[a[j]]];
        for(int j=i+i; j<=n; j+=i)
            f[i] -= f[j];
        for(int j=i; j<=n; j+=i)
            cnt[a[b[j]]]=0;
    }
    //for(int i=1;i<=n;i++){
        //cout<<cnt[i]<<" "<<f[i]<<endl;
    //}
    cout<<f[1]<<endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 40ms, 内存消耗: 3144K, 提交时间: 2023-01-19 20:55:16

#include<cstdio>
#include<vector>
int main()
{
	int n;scanf("%d",&n);
	std::vector<int> a(n+1),b(n+1),ab(n+1),ba(n+1),buab(n+1);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)ab[i]=a[b[i]],ba[i]=b[a[i]];
    std::vector<long long> f(n+1);
    for(int i=n;i>=1;i--)
    {
        for(int j=i;j<=n;j+=i)buab[ab[j]]++;
        for(int j=i;j<=n;j+=i)f[i]+=buab[ba[j]];
        for(int j=i*2;j<=n;j+=i)f[i]-=f[j];
        for(int j=i;j<=n;j+=i)buab[ab[j]]=0;
    }
	printf("%lld",f[1]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 102ms, 内存消耗: 4196K, 提交时间: 2019-08-18 12:47:01

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+2;
ll cnt[maxn],a[maxn],b[maxn],f[maxn];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=n;i>=1;i--){
        for(int j=i;j<=n;j+=i) cnt[a[b[j]]]++;
        for(int j=i;j<=n;j+=i) f[i] += cnt[b[a[j]]];
        for(int j=i+i;j<=n;j+=i) f[i] -= f[j];
        for(int j=i;j<=n;j+=i) cnt[a[b[j]]]--;
    }
    cout<<f[1]<<endl;
    return 0;
}