#Z0045. S数

---

一道很简单的模拟题，不知为何却足足做了将近2周。。。

---

一，TLE解法

#include 
using namespace std;
int f(int n)//返回n的所有数位相加之和
{
  int sum = 0;
  while(n > 0)
  {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
bool s(int n)//如果n是S数，返回1，不是返回0
{
  int ttt = n / 2,sn = f(n),st = 0;
//st:n的所有数位相加之和    sn:n的分解质因数后所有数位之和
  for(int i = 2; i <= ttt; i++)//分解质因数
  {
    if(n % i == 0)
    {
      int fs = 0;//fs记录n最多能被多少个i除
      while(n % i == 0) n /= i,fs++;
      st += f(i) * fs;
    }
  }
  if(sn == st) return 1;//如果n的所有数位相加之和==n的分解质因数后所有数位之和，返回1
  else return 0;
}
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    if(n == 0) break;
    for(int i = n + 1; i; i++)//枚举>n的数
    {
      if(s(i))//判断是否是S数
      {
        printf("%d\n",i);
        break;
      }
    }
  }
  return 0;
}

超时原因:分解质因数太慢了！此程序中分解质因数·时间复杂度为O(2*n)

---

二，AC解法

#include 
using namespace std;
int f(int n)
{
  int sum = 0;
  while(n > 0)
  {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
bool s(int n)
{
  int sn = f(n),st = 0;
  for(int i = 2; i <= n / i; i++)//原来要枚举n/2次，现在只需枚举sqrt(n)次即可
  {
    int fs = 0;
    while(n % i == 0) n /= i,fs++;
    st += f(i) * fs;
  }
  if(n > 1) st += f(n);//如果最后n仍没分解完,就直接把它看作质因数中的一个，有一次WA就是因为这一点
  if(sn == st) return 1;
  else return 0;
}
bool pri(int n)
{
  if(n < 2) return 0;
  if(n == 2) return 1;
  for(int i = 2; i <= n / i; i++)
    if(n % i == 0)
      return 0;
  return 1;
}
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    if(n == 0) break;
    for(int i = n + 1; i; i++)
    {
      if(pri(i)) continue;
//优化,因为题目中说了S数不包括质数，因为质数是没有办法分解的。有一次提交WA就是因为没加这一点
      if(s(i))
      {
        printf("%d\n",i);
        break;
      }
    }
  }
  return 0;
}

此程序中分解质因数·时间复杂度为O(sqrt(n))