牛客周赛Round64-B题题解

题目描述:

小红拿到了一个正整数，请你帮小红将其表示为幂（a^b）的形式。

输入描述:

一个正整数
2<=x<=10^5

输出描述:`

第一行输出x。
接下来每一行输出一个幂的表达式。
请按指数从小到大的顺序输出。

示例1

输入

16

输出

16
=16^1
=4^2
=2^4

解题思路:

这是一道思维题。我们拿到这个题首先看到数据范围是(10^{5),也就是O(n}2)的算法是肯定过不去的，那我们就需要优化我们的算法。

我们首先来想一个暴力的做法,也就是分别枚举底数a和指数b.

for(int i=1;i<=x;i++)
{
   for(int j=1;j<=x;j++)
   {
      if(pow(i,j)==x)
      {
        cout<<"="<<i<<"^"<<j<<endl;
      }
   }
}

这样是肯定会超时的。

那我们怎么优化呢?

我们先找一下规律，我们会发现底数a一定会是x的质因数，那我们先把x分解质因数。然后再把质因数存到一个数组里面就行了

也就是

 int count=0;

	 for(int i=1;i<=x/i;i++)
	 {
	 	  if(x%i==0)
	 	  {
	 	  	a[++count]=i;
		  }
	 }	
	 
	 
	 a[++count]=x;

指数我们发现，最多也就到根号x，不会比根号x还要大

AC 代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int  x;																																																																																																																						                                                                                                                                                                                                                                                                                                                                                    
int main()
{
	cin>>x;
	 
	 int t=x;
	 
	 int count=0;

	 for(int i=1;i<=x/i;i++)
	 {
	 	  if(x%i==0)
	 	  {
	 	  	a[++count]=i;
		  }
	 }	
	 
	 
	 a[++count]=x;
	 
	 
	 
	 x=t;
	 
	                                                                             
	cout<<x<<endl;
	
	for(int i=count;i>=1;i--)
	{
		for(int j=1;j<=sqrt(x);j++)
		{
			if(pow(a[i],j)==x)
			{
				cout<<"="<<a[i]<<"^"<<j<<endl;
			}
		}
	}

	
	             

	
	return 0;
}