牛客網——A找一找

連結：https://www.nowcoder.net/acm/contest/71/A

來源：牛客網

題目描述

給定n個正整數，請找出其中有多少個數x滿足：在這n個數中存在數y=kx，其中k為大于1的整數

輸入描述:

第一行輸入一個n 接下來一行輸入n個正整數a i

輸出描述:

輸出符合條件個數      

示例1

輸入

5
1 2 3 4 5      

輸出

2      

說明

5個數中1和2符合條件，1是後面每個數的因子，2是4的因子      

備注:

1≤n,a      

i

≤1000000      

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

const int inf = 0x3f3f3f3f;
const int maxn = 40000 + 20;
const int moder = 1e9 + 7;
const int K = 256;
const int MAXN=1000005;
int cnt[MAXN];

int main()
{
    int n;
    cin >> n;
    for(int i=0;i < n;i++)
    {
        int a;
        cin >> a;
        cnt[a]++;
    }

    int num = 0;
    for(int i=1;i < MAXN;i++)
    {
        if(cnt[i] > 0)
        {
            for(int j=2*i;j < MAXN;j=j+i)
            {
                if(cnt[j] > 0)
                {
                    num += cnt[i];
                    break;
                }

            }
        }
    }
    cout << num << endl;
    return 0;
}      

需要注意的是輸入的i可能會重複是以是用 cnt [i] ++;

轉載于:https://www.cnblogs.com/cunyusup/p/8409688.html