507. 完美數
題目鏈接
列舉所有因子
class Solution {
public:
bool checkPerfectNumber(int num) {
int sum=0;
for(int i=1;i<=num/i;i++){
if(num%i==0){
sum+=i;
if(i!=num/i) sum+=num/i;
}
}
sum-=num;
return sum==num;
}
};
公式求解
對num分解質因子以后有
那么他的因子其實就是幾個n1，幾個n2，幾個n3…的乘積（每一個因子選幾個，也可以不選），因為num的因子分解質因子的到的因子一定包含在num分解質因子的結果中，所以就會有因子和的一種演算法
然后乘積的每一項如何計算呢？我們可以利用秦九韶演算法
(就是每一次計算都把n1作為公因子提出來）
class Solution {
public:
bool checkPerfectNumber(int num) {
if(num==1) return false;
int m=num;
vector<pair<int,int>>res;
for(int i=2;i<=num/i;i++){
if(num%i==0){
int c=0;
while(num%i==0){
c++;
num/=i;
}
res.push_back({i,c});
}
}
int sum=1;
for(auto t:res){
int a=t.first,b=t.second,g=1;
for(int i=0;i<b;i++){
g=g*a+1;
}
sum=sum*g;
}
return sum==num;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342032.html
標籤：其他