SSL 2667_呵呵_模拟

发布于 2017-08-07  900 次阅读

题目描述

这天，小A得到了一个序列a[1],a[2]...a[n]，他想知道有多少个二元组(i,j)满足i!=j且a[i]是a[j]的因数。

 

思路

将每一个数放入一个桶里面，用一个数组 tot 记录每一个数字出现了多少次

对于每一个数记为i，我们可以暴力判断这个数的倍数是否存在

如果这个倍数存在的话，我们将这个数记为j

那么显然就有 $ans += tot[i] * tot[j]$

如果i有多个的话，找规律得 $ans += tot[i] * (tot[i] - 1)$

#include 
#include 
using namespace std;
#define maxn 2001001
int a[maxn], tot[maxn], t = 0, n, ans = 0, ma, xxx;
bool f[maxn], flag[maxn];
int main()
{
    scanf("%d", &n);
    ma = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        ma = ma > a[i] ? ma : a[i];
        tot[a[i]]++;
        f[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 0) continue;
        if (flag[a[i]] == 0)
        {
            flag[a[i]] = 1;
            ans += tot[a[i]] * (tot[a[i]] - 1);
            int j = a[i];
            while (j <= ma)
            {
                j += a[i];
                if (j > ma) break;
                ans += tot[a[i]] * tot[j];
            }
        }
    }
    printf("%d\n", ans);
}

 

]]>