3629: [JLOI2014]聪明的燕姿

3629: [JLOI2014]聪明的燕姿

题目链接

题目大意：令f(x)=Σi(i|x)给定n，求所有的x，使f(x)=n $题目大意：令f(x)=Σi (i|x) 给定n，求所有的x，使f(x)=n$

题解：有一个约数和公式……
d(i)=∏i(∑j=0kipji) $d(i)=\prod\limits_i (\sum\limits_{j=0}^{k_i} p_i^j)$
等比数列求和后得到
d(i)=∏ipki+1i−1pi−1 $d(i)=\prod\limits_i {p_i^{k_i+1}-1\over p_i -1}$

暴搜s的所有小于 s√ $\sqrt{s}$的质因子的次数，然后计算最后一个大质因子，然后通过这些质因子计算答案

ORZ题解1，ORZ题解2

我的收获：质因子大力搜强啊

#include <cstdio>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
using namespace std;  #define N 100000  int p[N+5],cnt,s,ans,num[N+5];  
bool flag[N+5];  void getprime()  
{  for(int i=2;i<=N;i++)  {  if(!flag[i]) p[++cnt]=i;  for(int j=1; i*p[j]<=N; j++)  {  flag[i*p[j]]=1;  if(i%p[j]==0) break;  }  }  
}  bool isprime(int x)  
{  if(x==1) return false;if(x<=N) return !flag[x];for(int i=1;p[i]*p[i]<=x;i++)  if(x%p[i]==0) return false;  return true;  
}  void dfs(int last,int now,int tot)  
{  if(tot==1){ num[++ans]=now; return; }  if(tot-1>p[last]&&isprime(tot-1))  num[++ans]=now*(tot-1);  for(int i=last+1; p[i]*p[i]<=tot; i++)  for(int tnum=p[i]+1,t=p[i]; tnum<=tot; t*=p[i],tnum+=t)//次方差公式化简一下if(tot%tnum==0)  dfs(i,now*t,tot/tnum);  
}  void work()
{ans=0;dfs(0,1,s);  cout<<ans<<endl;  sort(num+1,num+ans+1);  for(int i=1;i<=ans; i++)  printf("%d%c",num[i],i==ans?'\n':' ');
}int main()  
{  getprime();  while(scanf("%d",&s)!=EOF) work();return 0;
}