---
title: Uva13185 & Uva13194 DPA Numbers
tags: C++,Uva,Program,code,Uva13185,Uva13194,DPA Numbers
---
# Uva13185 & Uva13194 詳解
---
## 13185 DPA Numbers I
> [time=Mon, Jul 18, 2022 3:45 PM]
### 題目簡述:book:
體感難度：★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5096)
- T筆測資。
- 輸入正整數n，設x為n的所有因數總和減去n：
x=n 輸出 "perfect"
x<n 輸出 "deficient"
x>n 輸出 "abundant"
### 詳解:pencil2: (知識點：國小因數分解)
1~sqrt(n)找因數並相加，注意!當i=sqrt(n)時只加一次。
### 參考答案

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        int sum=0;
        for(int i=1;i*i<=n;i++)
            if(n%i==0)sum+=(i*i==n)?i:(i+n/i);
        if(sum-n==n)cout<<"perfect"<<endl;
        else if(sum-n<n)cout<<"deficient"<<endl;
        else cout<<"abundant"<<endl;
    }
}

---
## 13194 DPA Numbers II
> [time=Mon, Jul 18, 2022 4:45 PM]
### 題目簡述:book:
體感難度：★★★★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5096)
- [承上題](#13185_DPA_Numbers_I)
- 只是n很大很大 (2<=n<=10^12)
### 詳解:pencil2: (知識點：找質數+DFS)
#### 步驟一 找不大於sqrt(10^12)之所有質數
- **埃拉托斯特尼篩法**：
建立數字表並全部設為true
重複以下操作：
1. 找到還沒被設為false的最小數字
2. 將該數字放入質數陣列
3. 將表中所有該數的倍數設為false

vector<bool> prime_table(N,1);
vector<int> prime;
void build(){
    prime_table[0]=prime_table[1]=0;
    for(int i=2;i<N;i++){
        if(prime_table[i]){
            prime.push_back(i);
            for(int j=i+i;j<N;j+=i)
                prime_table[j]=0;
        }
    }
}

#### 步驟二 找質因數
利用質數陣列對n質因數分解

vector<pair<int,int>> vec; //pair<質因數,數量>
for(int i=0;n1>1&&i<prime.size();i++){		
    if(n1%prime[i]==0)vec.push_back({prime[i],0});
    while(n1%prime[i]==0){
        n1/=prime[i];
        vec[vec.size()-1].second++;
    }
}
if(n1>1) //n1>1代表n還存在一個大於sqrt(10^12)的質因數
    vec.push_back({n1,1});

#### 步驟三 找因數
用DFS窮舉所有因數 (解答中用回朔法優化)
### 參考答案

#include<bits/stdc++.h>
#define N 1000010
#define int long long
using namespace std;
vector<bool> prime_table(N,1);
vector<int> prime;
void build(){
    prime_table[0]=prime_table[1]=0;
    for(int i=2;i<N;i++){
        if(prime_table[i]){
            prime.push_back(i);
            for(int j=i+i;j<N;j+=i)
                prime_table[j]=0;
        }
    }
}
int dfs(vector<pair<int,int>>& v,int idx){
    if(idx==v.size()){
        int sum=1;
        for(int i=0;i<v.size();i++)sum*=pow(v[i].first,v[i].second);
        return sum;
    }
    int siz=v[idx].second,ans=0;
    for(int i=0;i<=siz;i++){
        v[idx].second=i;
        ans+=dfs(v,idx+1);
    }
    return ans;
}
signed main(){
    build();
    int t,n,n1,sum;
    cin>>t;
    while(t--){
        cin>>n;
        n1=n;
        vector<pair<int,int>> vec;
        for(int i=0;n1>1&&i<prime.size();i++){
            if(n1%prime[i]==0)vec.push_back({prime[i],0});
            while(n1%prime[i]==0){
                n1/=prime[i];
                vec[vec.size()-1].second++;
            }
        }
        if(n1>1)vec.push_back({n1,1});
        sum=dfs(vec,0);
        if(sum-n==n)cout<<"perfect"<<endl;
        else if(sum-n<n)cout<<"deficient"<<endl;
        else cout<<"abundant"<<endl;
	}
}

---