题解 P4397 【[JLOI2014]聪明的燕姿】

· · 题解

题解好少啊QAQ

安利一下

别人的题解

moyiii大佬的题解 https://www.cnblogs.com/moyiii-/p/7182894.html

一道显而易见的数学题，显而易见地我不会做。因为根本这个正解要用到的约数定理、约数和定理。唯一分解定理我都没学过，如果知道这些结论的话有没有推出答案的数学能力也未必。

唯一分解定理： 任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=P1^a1P2^a2…*Pn^an，这里P1<P2<…<Pn均为质数，其诸指数ai是正整数。这样的分解称为N的标准分解式。

约数和定理： 对于任意一个大于1的正整数N可以分解正整数：N=P1^a1*P2^a2…Pn^an，则由约数个数定理可知N的正约数有(a1+1)(a2+1)(a3+1)…(an+1)个，那么N的(a1+1)(a2+1)(a3+1)…(an+1)个正约数的和为f(N)=(P1^0+P1^1+P1^2+…P1^a1)(P2^0+P2^1+P2^2+…P2^a2)…(Pn^0+Pn^1+Pn^2+…Pn^an)。

用搜索将n分解为(p1^0+p1^1+…+p1^k1)(p2^0+p2^1+…+p2^k2)……(pn^0+pn^1+…+pn^kn),每一次成功的分解都会产生一个答案p1^k1p2^k2……*pn^kn。

搜索是很可行的。ad爷讲到对本题搜索的时间复杂度分析，当搜索的复杂度到了根号下根号n级别后就已经可以忽略了(高阶小量)，所以对这种搜索的时间复杂度只用考虑前几层。考试时常打搜索，有时接近正解，有时T得厉害，如果能学会这些分析应该会对搜索有更准确的估计吧。搜索之前要先处理出需要范围内的素数，还要有一个判断是否素数的函数。在搜索中要传递的是枚举到哪个素数(要求素数递增)、已有的乘积和、余下的需要分解的数。在搜索函数内先枚举素数，再枚举乘方，枚举到可以整除的就向下搜索。搜索停止的条件一是分解到只剩1，二是分解到一个大素数+1(直接在此处停止可以省去许多本来没有必要的枚举)。

数学问题确实千古难题，不管是奥赛还是文化课。到底是哪里难，也说不出个一二三。破釜沉舟，誓死不向数学低头。

有没有看晕捏？上代码

   #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int sj=100100;
ll s,m,ps,p[10000],res[sj],ge;
bool fp[sj]={1,1};
void xxs()
{
     for(int i=2;i<100000;i++)
     {
       if(!fp[i])
       {
          ps++;
          p[ps]=i;
       }
       for(int j=1;j<=ps&&i*p[j]<sj-5;j++)
       {
          fp[i*p[j]]=1;
          if(!(i%p[j]))
             break;
       }
     }
}
int pss(ll x)
{
    if(x==1) return 0;
    for(int i=1;p[i]*p[i]<=x;i++)
      if(!(x%p[i]))
        return 0;
    return 1;
}
void dfs(int l,ll ji,ll yu)
{
     if(yu==1)
     {
        ge++;
        res[ge]=ji;
        return;
     }
     long long temp,f;
     if((yu-1)>p[l]&&pss(yu-1))
     {
         ge++;
         res[ge]=(yu-1)*ji;
     }
     for(int i=l+1;p[i]*p[i]<=yu;i++)
     {
        temp=1;
        f=1;
        for(int j=1;temp<=yu;j++)
        {
           f*=p[i];
           temp+=f;
           if((yu%temp)==0)
             dfs(i,ji*f,yu/temp);
        }
     }
}
void cz()
{
    while(scanf("%lld",&s)==1)
    {
       memset(res,0,sizeof(res));
       ge=0;
       dfs(0,1,s);
       if(ge!=0)
       {
         sort(res+1,res+ge+1,less<int>());
         printf("%lld\n",ge);
         for(int i=1;i<ge;i++)
           printf("%lld ",res[i]);
         printf("%lld\n",res[ge]);
       }
       else
         printf("0\n");
    }
}
int main()
{
    xxs();
    cz();
    return 0;
}

南风知我意，吹梦到西洲。