TIOJ-1350 !!!!!!!!!!!!!!!!!!!!

TIOJ-1350 !!!!!!!!!!!!!!!!!!!!

AC code :

//By SCJ  

//TIOJ 1350  

#include<bits/stdc++.h>  

using namespace std;  

#define maxn 10000  

vector<int> p,h[maxn+2];  

bool np[maxn+2];  

map<int,int> mp[maxn+2];  

int main()  

{  

ios::sync_with_stdio(0);  

cin.tie(0);  

   np[0]=np[1]=1;  

   for(int i=2;i<=maxn;++i)  

   {  

       if(!np[i])  

       {  

           p.push_back(i);  

           for(int j=i*i;j<=maxn;j+=i) np[j]=1;  

       }  

   }  

   map<int,int> now;  

   for(int i=2;i<=maxn;++i)  

   {  

       int tp=i,pi=0;  

       while(tp>1)  

       {  

           int ct=0;  

           while(tp%p[pi]==0)  

           {  

               ct++;  

               tp/=p[pi];  

           }  

           if(ct) mp[i][p[pi]]+=ct;  

           pi++;  

       }  

   }  

   int T;cin>>T;  

   while(T--)  

   {  

       int ans[maxn+2]={0};  

       int n;cin>>n;  

       if(n==1) {cout<<"(1)\n";continue;}  

       bool flag=0;  

       for(int k=2;k<=n;++k)  

           for(auto i:mp[k])  

               ans[i.first]+=i.second;  

       for(int i=2;i<=maxn;++i)  

       {  

           if(ans[i])  

           {  

               if(flag) cout<<'*';flag=1;  

               if(ans[i]>1) cout<<'('<<i<<'^'<<ans[i]<<')';  

               else cout<<'('<<i<<')';  

           }  

       }  

       cout<<'\n';  

   }  

}