蓝桥杯算法训练VIP-友好数_c++(直接法、线性筛加约数和定理法）

直接法

参考代码:

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

int factor(int n){
    int s=0;
    for(int i=1;i<=n/2;i++) {
        if(n%i==0) 
			s+=i;
    }
    return s;
}
int main() {
	int a,b;
	cin>>a>>b;
	if(factor(a)==b && factor(b)==a)
		cout<<"yes";
	else
		cout<<"no";
	return 0;
}

运行情况：

约数和定理法

参考代码：

#include<bits/stdc++.h>

using namespace std;

int ysh(int a) {
	if(a<4) return 0;
	int count=1;
	vector<int> sign(a,1);
	int n=a;
	
	for(int i=2; i<a; ++i) {
		if(sign[i]) {
			//线性筛
			for(int j=2*i; j<n; j=j+i) {
				sign[j]=0;
			}
			//分解质因数(i,num) i^num*…… 
			if(n%i==0) {
				int num=0;
				while(n%i==0) {
					n=n/i;
					++num;
				}
				//约数和定理f(n)=(p1^0+p1^1+p1^2+)(p2^0+p2^1+p2^2+)……
				int sum=1;
				while(num) {
					int numi=num;
					int s=1;
					while(numi) {
						s*=i;
						--numi;
					}
					sum+=s;
					--num;
				}
				count*=sum;
				if(n==0)
					break;
			}
		}
	}
	return count-a;
}

运行情况：