（紀中）2181. 羊羊整除（div）

(File IO): input:div.in output:div.out

時間限制: 1000 ms 空間限制: 131072 KB 具體限制

Goto ProblemSet

題目描述

羊年到了，村長開始教小羊學習 P a s c a l Pascal Pascal語言，剛開始學習四則運算。村長在白闆上寫下兩個整數 16 16 16和 3 3 3，問小羊們，有 16 16 16隻羊，平均分到 3 3 3個羊村，每個羊村分到的數量必須相同，這個配置設定的數量最大是多少？小羊們很快就得到了答案，每個羊村分到 5 5 5隻，有 1 1 1隻羊就隻能落單了。村長在白闆上寫下 5 5 5。沒錯，這個就是 D i v Div Div(整除)的用法！

為了檢驗小羊們是否掌握了整除運算，村長要求小羊們輪流從白闆上任意選取兩個不同的數，由大數整除小數，若所得結果沒有出現在白闆上，就将該值寫在白闆上。直到小羊們再也找不到沒出現過的整數。

雖然這樣上課很鍛煉小羊們的運算能力，但是課堂時間有限。為了控制課堂時間，村長想要知道，根據目前白闆上的數字，最終白闆上會出現幾個數字？現在請你幫他編寫一個程式快速計算一下吧！

輸入

第一行一個整數 N N N，表示目前白闆上出現的整數個數。

第二行 N N N個整數，中間用空格分隔，表示目前在白闆上的數字，保證每個數字都不相同。

輸出

輸出一個整數，表示最終白闆上數字的個數。

樣例輸入

【樣例輸入1】

2

16 3

【樣例輸入2】

3

17 2 1

樣例輸出

【樣例輸出1】

4

【樣例輸出2】

5

資料範圍限制

50 50 50%的資料， N < = 50 N<=50 N<=50；

100 100 100%的資料， N < = 100 ， 1 < = a i < = 100 N<=100，1<=ai<=100 N<=100，1<=ai<=100。

提示

【樣例 1 1 1解釋】

選擇 16 16 16和 3 3 3，寫下 5 5 5；選擇 5 5 5和 3 3 3，寫下 1 1 1；共 16 ， 3 ， 5 ， 1 16，3，5，1 16，3，5，1，四個整數。

【樣例2解釋】

選擇 17 17 17和 2 2 2，寫下 8 8 8；再選擇 8 8 8和 2 2 2，寫下 4 4 4；共 17 ， 2 ， 8 ， 4 ， 1 17，2，8，4，1 17，2，8，4，1，五個整數。

解題思路

資料較小，可以開一個桶存出現過的數字，是以可以n^2暴力枚舉x，y得出的值，得出的結果再次存入桶中。因為x/y一定比x小，是以可以一次得出結果，最後統計所有數字。

代碼

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
int n,a[105],f[105],ans;
int main(){
   freopen("div.in","r",stdin);
   freopen("div.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[a[i]]=1;
    }
    for(int i=100;i>=1;i--)
    {
        if(f[i])
        {
           for(int j=i-1;j>=1;j--)
           if(f[j])
           f[i/j]=1;
        }
    }
    ans=0;
    for(int i=1;i<=100;i++)
        if(f[i]==1)
            ans++;
    printf("%d",ans);
}