[COGS371]亲和数解题报告

本文主要是介绍[COGS371]亲和数解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题感觉还是挺好的。
这个题吧，有两种解法。第一种吧比较暴力算是卡过的，第二种常数很小，要比第一种好很多也高端很多啦。
但是由于我对于第二种解法涉及的一些知识不是很熟悉，导致我还是放弃了它，选择了更熟悉的第一种；后来看了别人的代码才开始重新想第二种。

解法一：
暴力枚举[A,B]所有元素，暴力算出其中每个的因数和；如果其因数和大于本身，就再算一下那个数的因数和判断一下即可。
一个因数个数是期望 $O(log_2n)$ 的，由于是连续的一段，使得这个期望变得比较靠谱。
期望时间复杂度 $O((B-A)(\frac {N^\frac12} {ln N^\frac12}+lnN))$
解法二：
积性易知，我起初想的是用线筛递推，发现卡T了（积性函数只学过线筛递推）。。但是实际上求积性函数只需要花费分解质因数的时间代价即可。
所以得到了最坏时间复杂度 $O((B-A)(\frac {N^\frac12} {ln N^\frac12}+log_2N))$ 的算法。
代码（解法一）：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 10000
int prime[10000000];
#include<bitset>
#include<iostream>
bitset<MAXN> p;
int pri[30],sum[30],tot,T;
typedef long long LL;
void dfs(int x,int now){if(x==tot){if(T>-1E9){T+=now;//cout<<now<<" ";if(T>1E8)T=-1E9;}return;}dfs(x+1,now);for(int i=sum[x];i--;)dfs(x+1,now*=pri[x]);
}
int work(int x){tot=0,T=-x;//cout<<x<<":";for(int i=1;i<prime[0]&&prime[i]*prime[i]<=x;++i)if(x%prime[i]==0){pri[tot]=prime[i],sum[tot]=0;for(;x%prime[i]==0;x/=prime[i])++sum[tot];++tot;}if(x!=1)pri[tot]=x,sum[tot++]=1;dfs(0,1);//cout<<"->"<<T<<endl;return T;
}
int main(){freopen("amicable.in","r",stdin);freopen("amicable.out","w",stdout);int i,j;prime[0]=1;for(i=2,j;i<MAXN;++i){if(~p[i])prime[prime[0]++]=i;for(j=1;j<prime[0]&&i*prime[j]<MAXN;++j){p[i*prime[j]]=1;if(i%prime[j]==0)break;}}int A,B,x,ans,Ans=0;scanf("%d%d",&A,&B);for(j=A;j<=B;++j){//cout<<"-------"<<j<<"---------\n";ans=work(j);if(ans>j&&work(ans)==j)++Ans;}printf("%d\n",Ans);
}

代码（解法二）：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 10000
int prime[100000];
#include<bitset>
#include<iostream>
bitset<MAXN> p;
typedef long long LL;
int work(int x){LL ans=1;int sum,X=x;for(int i=1;i<prime[0]&&ans&&prime[i]*prime[i]<=x;++i)if(x%prime[i]==0){sum=1;for(;x%prime[i]==0;x/=prime[i])sum*=prime[i];ans*=((LL)prime[i]*sum-1)/(prime[i]-1);if(ans>1E9)ans=0;}if(x!=1){ans*=(x+1);if(ans>1E9)ans=0;}return ans-X;
}
int main(){freopen("amicable.in","r",stdin);freopen("amicable.out","w",stdout);int i,j;prime[0]=1;for(i=2,j;i<MAXN;++i){if(~p[i])prime[prime[0]++]=i;for(j=1;j<prime[0]&&i*prime[j]<MAXN;++j){p[i*prime[j]]=1;if(i%prime[j]==0)break;}}int A,B,ans,Ans=0;scanf("%d%d",&A,&B);for(j=A;j<=B;++j){ans=work(j);if(ans>j&&work(ans)==j)++Ans;}printf("%d\n",Ans);
}