---
title: CPE二星筆記
tags: C++, CPE, Program, code
---
# CPE二星筆記:pencil:
---
## 目錄
| 001~100 | | 101~200 | | 201~300 | |
| ------- | --- | ------- | --- | ------------------------------ | --------------------------------------- |
| 151 | | 10233 | | 11043 | |
| 245 | | 10236 | | 11051 | |
| 255 | | 10238 | | 11056 | |
| 294 | | 10252 | | 11057 | |
| 337 | | 10256 | | 11067 | |
| 374 | | 10263 | | 11076 | |
| 378 | | 10264 | | 11078 | |
| 397 | | 10266 | | 11086 | |
| 406 | | 10267 | | 11093 | |
| 495 | | 10283 | | 11094 | |
| 514 | | 10284 | | 11096 | |
| 516 | | 10286 | | 11115 | |
| 534 | | 10287 | | 11121 | |
| 536 | | 10289 | | 11157 | |
| 540 | | 10293 | | 11235 | |
| 572 | | 10295 | | 11241 | |
| 612 | | 10297 | | 11264 | |
| 657 | | 10298 | | 11286 | |
| 674 | | 10299 | | 11287 | |
| 679 | | 10301 | | 11308 | |
| 686 | | 10302 | | 11326 | |
| 696 | | 10305 | | 11335 | |
| 722 | | 10311 | | 11340 | |
| 748 | | 10312 | | 11344 | |
| 821 | | 10315 | | 11348 | |
| 900 | | 10322 | | 11350 | |
| 924 | | 10325 | | 11360 | |
| 967 | | 10327 | | 11369 | |
| 991 | | 10333 | | 11396 | |
| 993 | | 10334 | | 11403 | |
| 997 Show the Sequence | [link](#997_Show_the_Sequence) | 10336 | | 11412 | |
| 1200 | | 10338 | | 11417 |[link](#11417_GCD) |
| 1210 | | 10339 | | 11418 | |
| 1262 | | 10341 | | 11462 | |
| 1644 | | 10343 | | 11475 | |
| 1730 | | 10344 | | 11480 | |
| 1753 | | 10345 | | 11484 | |
| 10001 | | 10347 | | 11505 | |
| 10002 | | 10348 | | 11507 | |
| 10004 Bicoloring |[link](#10004_Bicoloring) | 10352 | | 11508 | |
| 10006 | | 10360 | | 11515 | |
| 10009 | | 10368 | | 11518 | |
| 10010 | | 10371 | | 11519 | |
| 10013 Super long sums | [link](#10013_Super_long_sums) | 10372 | | 11520 | |
| 10014 | | 10382 | | 11536 | |
| 10015 | | 10405 | | 11538 | |
| 10016 | | 10406 | | 11550 | |
| 10017 | | 10407 | | 11583 | |
| 10020 | | 10408 | | 11586 | |
| 10028 | | 10427 | | 11609 | |
| 10034 | | 10432 | | 11614 | |
| 10039 | | 10440 | | 11615 | |
| 10040 | | 10450 | | 11616 | |
| 10060 | | 10466 | | 11629 | |
| 10061 | | 10489 | | 11683 | |
| 10063 | | 10494 | | 11692 | |
| 10064 | | 10497 | | 11703 | |
| 10066 | | 10504 | | 11714 | |
| 10070 | | 10508 | | 11729 | |
| 10077 | | 10523 | | 11730 | |
| 10098 | | 10527 | | 11742 | |
| 10100 | | 10535 | | 11847 | |
| 10102 | | 10555 | | 11849 | |
| 10104 | | 10563 | | 11850 | |
| 10106 | | 10579 | | 11879 | |
| 10107 | | 10583 | | 11898 | |
| 10110 | | 10596 | | 11953 | |
| 10114 | | 10608 | | 11957 | |
| 10115 | | 10611 | | 11991 | |
| 10116 | | 10625 | | 11995 | |
| 10125 | | 10666 | | 11997 | |
| 10127 | | 10670 | | 12160 | |
| 10137 | | 10673 | | 12207 | |
| 10138 | | 10684 | | 12382 | |
| 10140 | | 10700 | | 12406 Help Dexter | [link](#12406_Help_Dexter) |
| 10141 | | 10718 | | 12455 Bars | [link](#12455_Bars) |
| 10145 | | 10738 | | 12592 Slogan Learning of Princess | [link](#12592_Slogan_Learning_of_Princess) |
| 10142 | | 10730 | | 12545 Bits Equalizer | [link](#12545_Bits_Equalizer) |
| 10146 | | 10763 | | 12694 Meeting Room Arrangement | [link](#12694_Meeting_Room_Arrangement) |
| 10152 | | 10815 | | 12705 Breaking Board | [link](#12705_Breaking_Board) |
| 10160 | | 10820 | | 12797 Letters | [詳解](#12797_Letters) |
| 10161 | | 10858 | | 12844 | |
| 10167 | | 10871 | | 13185 DPA Numbers I | [詳解](#13185_DPA_Numbers_I) |
| 10172 | | 10881 | | 13194 DPA Numbers II | [詳解](#13194_DPA_Numbers_II) |
| 10174 | | 10887 | | | |
| 10176 | | 10901 | | | |
| 10180 | | 10902 | | | |
| 10182 | | 10910 | | | |
| 10192 | | 10915 | | | |
| 10193 | | 10916 | | | |
| 10194 | | 10920 | | | |
| 10195 | | 10924 | | | |
| 10196 | | 10926 | | | |
| 10197 | | 10930 | | | |
| 10200 | | 10936 | | | |
| 10205 | | 10940 | | | |
| 10220 | | 10959 | | | |
| 10223 | | 11013 | | | |
| 10225 | | 11039 | | | |
| 10227 | | 11040 | | | |
---
## 151
## 245
## 255
## 294
## 337
## 374
## 378
## 397
## 406
## 495
## 514
## 516
## 534
## 536
## 540
## 572
## 612
## 657
## 674
## 679
## 686
## 696
## 722
## 748
## 821
## 900
## 924
## 967
## 991
## 993
## 997_Show_the_Sequence
### 題目簡述:book:
體感難度：★★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=938)
### 詳解:pencil2:(知識點：找規律)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;
int N,x;
char ch;
while(cin>>str>>N){
stack<char> stk;
vector<char> op;
vector<int> v0,v1;
stringstream ss(str);
while(ss>>ch){
if(ch=='*'||ch=='+')
op.push_back(ch);
else if(isdigit(ch)||ch=='-'){
ss.unget();
ss>>x;
v0.push_back(x);
}
}
reverse(v0.begin(),v0.end());
reverse(op.begin(),op.end());
v1=vector<int>(v0.size(),0);
for(int j=1;j<v0.size();j++){
if(op[j-1]=='*')
v0[j]=v0[j-1]*v0[j];
}
cout<<*v0.rbegin();
for(int i=1;i<N;i++){
v1[0]=v0[0];
for(int j=1;j<v1.size();j++){
if(op[j-1]=='+')
v1[j]=v0[j-1]+v0[j];
else
v1[j]=v1[j-1]*v0[j];
}
cout<<' '<<*v1.rbegin();
v0.swap(v1);
}
cout<<'\n';
}
}
```
## 1200
## 1210
## 1262
## 1644
## 1730
## 1753
## 10001
## 10002
## 10004_Bicoloring
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=945)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,a,b;
while(cin>>n,n){
cin>>m;
vector<int> g[210],vis(210);
while(m--){
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
try{
for(int i=0;i<n;i++){
stack<int> s;
if(vis[i]==0)
vis[i]=1,s.push(i);
while(s.size()){
int node=s.top();
s.pop();
for(int child:g[node]){
if(vis[child]==0){
s.push(child);
vis[child]=(vis[node]==1 ? 2:1);
}
else if(vis[child]==vis[node]){
throw 1;
}
}
}
}
cout<<"BICOLORABLE.\n";
}
catch(int e){
cout<<"NOT BICOLORABLE.\n";
}
}
}
```
## 10006
## 10009
## 10010
## 10013_Super_long_sums
體感難度：★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=938)
### 詳解:pencil2:(知識點：大數加法)
### 參考程式碼
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=954&mosmsg=Submission+received+with+ID+28272917)
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
char ch;
cin>>t;
while(t--){
string s1,s2,c,ans;
int a,b,n;
cin>>n;
while(n--){
cin>>a>>b;
s1.push_back(a);
s2.push_back(b);
}
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
ans=c=string(s1.size()+1,0);
for(int i=0;i<s1.size();i++){
c[i+1]=(s1[i]+s2[i]+c[i])/10;
ans[i]=(s1[i]+s2[i]+c[i])%10;
}
if(*c.rbegin()==char(1))
*ans.rbegin()=1;
else
ans.pop_back();
for(int i=ans.size()-1;i>=0;i--)
cout<<int(ans[i]);
cout<<'\n';
if(t!=0)
cout<<'\n';
}
}
```
### python速解
```python=
t=int(input())
for tt in range(t):
ch=input()
n=int(input())
ans=0
for i in range(n):
a,b=map(int,input().split())
ans+=(a+b)*10**(n-1-i)
print(ans,end="\n\n")
```
## 10014
## 10015
## 10016
## 10017
## 10020
## 10028
## 10034
## 10039
## 10040
## 10060
## 10061
## 10063
## 10064
## 10066
## 10070
## 10077
## 10098
## 10100
## 10102
## 10104
## 10106
## 10107
## 10110
## 10114
## 10115
## 10116
## 10125
## 10127
## 10137
## 10138
## 10140
## 10141
## 10142
## 10145
## 10146
## 10152
## 10160
## 10161
## 10167
## 10172
## 10174
## 10176
## 10180
## 10182
## 10192
## 10193
## 10194
## 10195
## 10196
## 10197
## 10200
## 10205
## 10220
## 10223
## 10225
## 10227
## 10233
## 10236
## 10238
## 10252
## 10256
## 10263
## 10264
## 10266
## 10267
## 10283
## 10284
## 10286
## 10287
## 10289
## 10293
## 10295
## 10297
## 10298
## 10299
## 10301
## 10302
## 10305
## 10311
## 10312
## 10315
## 10322
## 10325
## 10327
## 10333
## 10334
## 10336
## 10338
## 10339
## 10341
## 10343
## 10344
## 10345
## 10347
## 10348
## 10352
## 10360
## 10368
## 10371
## 10372
## 10382
## 10405
## 10406
## 10407
## 10408
## 10427
## 10432
## 10440
## 10450
## 10466
## 10489
## 10494
## 10497
## 10504
## 10508
## 10523
## 10527
## 10535
## 10555
## 10563
## 10579
## 10583
## 10596
## 10608
## 10611
## 10625
## 10666
## 10670
## 10673
## 10684
## 10700
## 10718
## 10730
## 10738
## 10763
## 10815
## 10820
## 10858
## 10871
## 10881
## 10887
## 10901
## 10902
## 10910
## 10915
## 10916
## 10920
## 10924
## 10926
## 10930
## 10936
## 10940
## 10959
## 11013
## 11039
## 11040
## 11043
## 11051
## 11056
## 11057
## 11067
## 11076
## 11078
## 11086
## 11093
## 11094
## 11096
## 11115
## 11121
## 11157
## 11235
## 11241
## 11264
## 11286
## 11287
## 11308
## 11326
## 11335
## 11340
## 11344
## 11348
## 11350
## 11360
## 11369
## 11396
## 11403
## 11412
## 11417_GCD
體感難度：★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2412&mosmsg=Submission+received+with+ID+28279037)
### 詳解:pencil2:(知識點：大數加法)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin>>n,n){
long long int ans=0;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
ans+=__gcd(i,j);
cout<<ans<<'\n';
}
}
```
## 11418
## 11462
## 11475
## 11480
## 11484
## 11505
## 11507
## 11508
## 11515
## 11518
## 11519
## 11520
## 11536
## 11538
## 11550
## 11583
## 11586
## 11609
## 11614
## 11615
## 11616
## 11629
## 11683
## 11692
## 11703
## 11714
## 11729
## 11730
## 11742
## 11847
## 11849
## 11850
## 11879
## 11898
## 11953
## 11957
## 11991
## 11995
## 11997
## 12160
## 12207
## 12382
## 12406_Help_Dexter
> [time=Mon, Jul 18, 2022 10:16 PM]
### 題目簡述:book:
體感難度：★★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3837)
### 詳解:pencil2:(知識點：利用二進位窮舉)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t,p,q;
int pow2[18]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
cin>>t;
for(int d=1;d<=t;d++){
cin>>p>>q;
set<int> s;
for(int i=0;i<pow2[p];i+=2){
int num=0,k=i,digits=1;
for(int r=1;digits<=p;r*=10,digits++){
num+=(k&1?1:2)*r;
k>>=1;
}
if(num%pow2[q]==0)s.insert(num);
}
cout<<"Case "<<d<<": ";
if(s.size()==0)cout<<"impossible"<<endl;
else if(s.size()==1)cout<<*s.begin()<<endl;
else cout<<*s.begin()<<' '<<*s.rbegin()<<endl;
}
}
```
---
## 12455_Bars
> [time=Mon, Jul 18, 2022 8:21 PM]
### 題目簡述:book:
體感難度：★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3886)
### 詳解:pencil2:(知識點：利用二進位窮舉)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,n,p;
cin>>t;
while(t--){
bool OK=0;
cin>>n>>p;
vector<int> v(p);
for(int i=0;i<p;i++)cin>>v[i];
for(int i=0;i<pow(2,p)&&!OK;i++){
int k=i,len=0;
for(int cur=0;k;cur++){
if(k%2)len+=v[cur];
k>>=1;
}
OK=(len==n);
}
cout<<(OK?"YES":"NO")<<endl;
}
}
```
---
## 12592_Slogan_Learning_of_Princess
> [time=Tue, Jul 19, 2022 7:14 PM]
### 題目簡述:book:
體感難度：0
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4270)
### :pencil:(知識點 : map)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
string a,b;
map<string,string> m;
cin>>n>>ws;
while(n--){
getline(cin,a);
getline(cin,b);
m[a]=b;
}
cin>>n>>ws;
while(n--){
getline(cin,a);
cout<<m[a]<<endl;
}
}
```
---
## 12545_Bits_Equalizer
> [time=Mon, Jul 18, 2022 8:21 PM]
### 題目簡述:book:
體感難度：★★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3990)
### 詳解:pencil2:(知識點：貪心)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
for(int k=1;k<=n;k++){
string s,t;
int step=0,d=0,add=0; //d=sumT-sumS
cin>>s>>t;
for(int i=0;i<s.size();i++)d+=(t[i]=='1')-(s[i]=='1');
if(d<0){
cout<<"Case "<<k<<": -1"<<endl;
continue;
}
for(int i=0;i<s.size();i++){ //處理'?'
if(s[i]!='?')continue;
if(d>0 && t[i]=='1')s[i]='1',d--;
else s[i]='0';
step++;
}
for(int i=0;i<s.size()&&d>0;i++){ //補'1'
if(s[i]=='0'&&t[i]=='1'){
s[i]='1';
d--,step++;
}
}
for(int i=0;i<s.size();i++) // XOR
add+=!(s[i]==t[i]);
step+=(add/2);
cout<<"Case "<<k<<": "<<step<<endl;
}
}
```
---
## 12694_Meeting_Room_Arrangement
> [time=Mon, Jul 18, 2022 7:14 PM]
### 題目簡述:book:
體感難度：★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4432)
### 詳解:pencil2:(知識點：工作排程貪心)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,a,b;
cin>>t;
while(t--){
vector<pair<int,int>> v; //pair<end,start>
while(cin>>a>>b,a||b)v.push_back({b,a});
sort(v.begin(),v.end());
int back=v[0].first,ans=1;
for(int i=1;i<v.size();i++){
if(v[i].second>=back){
back=v[i].first;
ans++;
}
}
cout<<ans<<endl;
}
}
```
---
## 12705_Breaking_Board
> [time=Mon, Jul 18, 2022 6:45 PM]
### 題目簡述:book:
體感難度：★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4443)
### 詳解:pencil2:(知識點：map+權重排序)
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t>>ws;
while(t--){
int sum=0;
string s;
getline(cin,s);
int cost[36]={2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8,8,9,9,9,9,10,10,10,11,11,12};
map<char,int> num,index;
priority_queue<pair<int,char>> pq;
for(char &e:s)if(e!=' ')num[e]++;
for(auto &it:num) pq.push({it.second,it.first});
for(int i=0;pq.size();i++){
index[pq.top().second]=i;
pq.pop();
}
for(char &e:s)if(e!=' ')sum+=cost[index[e]];
cout<<sum<<endl;
}
}
```
---
## 12797_Letters
> [time=Mon, Jul 18, 2022 12:01 PM]
### 題目簡述:book:
體感難度：★★★
[Browse Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=823&page=show_problem&problem=4662)
- 多筆測資EOF板。
- 在n*n的字元陣列中，找(0,0)->(n-1,n-1)之最短路徑，其中路徑上不可同時存在同字母之大小寫。
### 詳解:pencil2: (知識點：二進位+BFS)
#### 步驟一 找字母大小寫分布
窮舉路徑上字母大小寫分布可能(0：只允許小寫 1：只允許大寫)
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ------ | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |
| **letter** | **A** | **B** | **C** | **D** | **E** | **F** | **G** | **H** | **J** | **I** |
| i=0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| i=1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| i=2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| i=3 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
```cpp=
//利用二進位性質可窮舉vector<bool> t(10)之所有排列
for(int i=0;i<1024;i++){
vector<bool> t(10);
for(int cur=0,k=i;k;k>>=1)t[cur++]=k&1;
}
```
#### 步驟二 找最短路徑
對每一種大小寫分布可能分別進行BFS找出最短路徑。
### 參考程式碼
```cpp=
#include<bits/stdc++.h>
#define oo 10010
using namespace std;
typedef tuple<int,int,int> tiii;
int dr[4]{-1,0,0,1},dc[4]{0,-1,1,0},ans;
int isup(char &ch){
return (ch<97);
}
int toi(char &ch){
return isup(ch)?ch-65:ch-97;
}
void bfs(vector<string> v,vector<bool> &t,int n){
queue<tiii> q;
int flag=1,r,c,step;
if(isup(v[0][0])==t[toi(v[0][0])])q.push(tiii{0,0,1});
while(q.size()&&flag){
tie(r,c,step)=q.front();
q.pop();
for(int k=0;k<4&&flag;k++){
int r1=r+dr[k],c1=c+dc[k];
if(r1>=0 && r1<n && c1>=0 && c1<n && v[r1][c1]!=0 && isup(v[r1][c1])==t[toi(v[r1][c1])]){
if(r1==n-1 && c1==n-1){
ans=min(ans,step+1);
flag=0;
}
v[r1][c1]=0;
q.push(tiii{r1,c1,step+1});
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
while(cin>>n){
ans=oo;
vector<string> v(n,"");
for(int i=0;i<n;i++)cin>>v[i];
for(int i=0;i<1024;i++){
vector<bool> t(10);
for(int cur=0,k=i;k;k>>=1)t[cur++]=k&1;
bfs(v,t,n);
}
cout<<(ans!=oo?ans:-1)<<endl;
}
}
```
---
## 12844
---
## 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)時只加一次。
### 參考答案
```cpp=
#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
```cpp=
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質因數分解
```cpp=
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窮舉所有因數 (解答中用回朔法優化)
### 參考答案
```cpp=
#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;
}
}
```
---
Sign in with Wallet
Connect another wallet