20240405比赛总结

寄的很惨

T1 [JLOI2014] 聪明的燕姿

https://gxyzoj.com/d/hzoj/p/3672

敲个警钟，千万不要用一些奇怪的方法写自己会的题，不然大概率会一分不剩

由小学奥数知识，约数和的求法为\(\prod (1+p_i^2+p_i^3+\dots+p_i^{a_i})\)

所以，可以先线性预处理出约数和，再直接统计，时间复杂度\(O(nk)\),显然会T

考虑优化，显然，约数和也是一个乘积所以可以枚举其因子，注意，同一个p只可以使用一次

所以可以dfs，记录当前的答案和剩余的数，但是，2e9以内的质数不会少于5e7个，所以，还要优化

因为一个数n中不会出现两个超过\(\sqrt n\)的因数，所以，考虑只枚举\(\sqrt{10^9}\)以内的因数，其余暴力判断即可

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e9;
int s,idx,ans,t[100005];
bool get_prime(int x)
{
	if(x==1||x==0) return 0;
	for(int i=2;i<=x/i;i++)
	{
		if(x%i==0) return 0;
	}
	return 1;
}
int cnt,p[50005];
bool vis[50005];
void dfs(int x,int num,int id)
{
	//printf("%d %d %d\n",x,num,id);
	if(x==1)
	{
		t[++ans]=num;
		return;
	}
	for(int i=id;i<=cnt&&p[i]*p[i]<=x;i++)
	{
		ll tmp=1,sum=1;
		for(int j=1;;j++)
		{
			tmp*=p[i];
			sum+=tmp;
			if(sum<=x)
			{
				if(x%sum==0)
				{
					dfs(x/sum,num*tmp,i+1);
				}
			}
			else break;
		}
	}
	if(get_prime(x-1)&&x-1&&x-1>=p[id]) t[++ans]=(x-1)*num;
}
int main()
{
	for(int i=2;i<=50000;i++)
	{
		if(!vis[i]) p[++cnt]=i;
		for(int j=1;i*p[j]<=50000;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
	while(cin>>s)
	{
		ans=0;
		dfs(s,1,1);
		sort(t+1,t+ans+1);
		int tmp=ans;
		for(int i=1;i<=ans;i++)
		{
			if(t[i]==t[i-1]) tmp--;
		}
		printf("%d\n",tmp);
		for(int i=1;i<=ans;i++)
		{
			if(t[i]!=t[i-1]) printf("%d ",t[i]);
		}
		if(ans)
		printf("\n");
	}
	return 0;
}