代码

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN=5e5+128;

int cnt[MAXN],next[MAXN];
bool isruning[MAXN];    //利用邻接表来存数
int m=0;

int head[MAXN];

int main()
{
    //freopen("/home/noilinux/Desktop/day1_B/pair/pair2.in","r",stdin);

    int n;scanf(" %d",&n);

    for(int i=0;i<n;i++)
    {
        int t;
        scanf(" %d",&t);
        ++m;
        next[m]=head[t];
        head[t]=m;
    }

    int ans=0;

    for(int i=1;i<MAXN;i++)
    {
        for(int j=head[i];j!=0;j=next[j])
        {
            isruning[j]=true;

            for(int k=i;k<MAXN;k+=i)
            {
                for(int l=head[k];l!=0;l=next[l])
                {
                    if(!isruning[l])
                    {
                        cnt[l]++;
                        ans++;
                      }
                }
            }
            isruning[j]=false;
        }
    }

    printf("%d",ans);

}

Last modification:April 18th, 2021 at 11:46 am