fork download 
  1. #include <list>
  2. #include <string>
  3. #include <iomanip>
  4. #include <sstream>
  5. #include <iostream>
  6. using namespace std;
  7.  
  8. unsigned short T[100000];
  9. struct PrimeNumber { unsigned prime[9]; unsigned count; } Primes[]=
  10.   { 
  11.    {{  1,  2,  4,  8, 16, 32, 64,128,256}},
  12.    {{  1,  3,  9, 27, 81,243}},
  13.    {{  1,  5, 25,125}},
  14.    {{  1,  7, 49,343}},
  15.    {{  1, 11,121}},
  16.    {{  1, 13,169}},
  17.    {{  1, 17,289}},
  18.    {{  1, 19,361}},
  19.    {{  1, 23}},
  20.    {{  1, 29}},
  21.    {{  1, 31}},
  22.    {{  1, 37}},
  23.    {{  1, 41}},
  24.    {{  1, 43}},
  25.    {{  1, 47}},
  26.    {{  1, 53}},
  27.    {{  1, 59}},
  28.    {{  1, 61}},
  29.    {{  1, 67}},
  30.    {{  1, 71}},
  31.    {{  1, 73}},
  32.    {{  1, 79}},
  33.    {{  1, 83}},
  34.    {{  1, 89}},
  35.    {{  1, 97}},
  36.    {{  1,101}},
  37.    {{  1,103}},
  38.    {{  1,107}},
  39.    {{  1,109}},
  40.    {{  1,113}},
  41.    {{  1,127}},
  42.    {{  1,131}},
  43.    {{  1,137}},
  44.    {{  1,139}},
  45.    {{  1,149}},
  46.    {{  1,151}},
  47.    {{  1,157}},
  48.    {{  1,163}},
  49.    {{  1,167}},
  50.    {{  1,173}},
  51.    {{  1,179}},
  52.    {{  1,181}},
  53.    {{  1,191}},
  54.    {{  1,193}},
  55.    {{  1,197}},
  56.    {{  1,199}},
  57.    {{  1,211}},
  58.    {{  1,223}},
  59.    {{  1,227}},
  60.    {{  1,229}},
  61.    {{  1,233}},
  62.    {{  1,239}},
  63.    {{  1,241}},
  64.    {{  1,251}},
  65.    {{  1,257}},
  66.    {{  1,263}},
  67.    {{  1,269}},
  68.    {{  1,271}},
  69.    {{  1,277}},
  70.    {{  1,281}},
  71.    {{  1,283}},
  72.    {{  1,293}},
  73.    {{  1,307}},
  74.    {{  1,311}},
  75.    {{  1,313}},
  76.    {{  1,317}},
  77.    {{  1,331}},
  78.    {{  1,337}},
  79.    {{  1,347}},
  80.    {{  1,349}},
  81.    {{  1,353}},
  82.    {{  1,359}},
  83.    {{  1,367}},
  84.    {{  1,373}},
  85.    {{  1,379}},
  86.    {{  1,383}},
  87.    {{  1,389}},
  88.    {{  1,397}},
  89.    {{  1,401}},
  90.    {{  1,409}},
  91.    {{  1,419}},
  92.    {{  1,421}},
  93.    {{  1,431}},
  94.    {{  1,433}},
  95.    {{  1,439}},
  96.    {{  1,443}},
  97.    {{  1,449}},
  98.    {{  1,457}},
  99.    {{  1,461}},
  100.    {{  1,463}},
  101.    {{  1,467}},
  102.    {{  1,479}},
  103.    {{  1,487}},
  104.    {{  1,491}},
  105.    {{  1,499}},
  106.   };
  107. const unsigned PrimeSize=sizeof(Primes)/sizeof(*Primes);
  108. struct ResultValues { string result; unsigned power[PrimeSize]; bool have; } Values[501];
  109.  
  110. int main()
  111.   {
  112.    ios::sync_with_stdio(false);
  113.    unsigned N;
  114.    cin>>N;
  115.    for(unsigned i=0;i<N;++i)
  116.      {
  117.       unsigned short value;
  118.       cin>>value;
  119.       T[i]=value;
  120.       if(!Values[value].have)
  121.         {
  122.          unsigned short V=value; 
  123.          for(unsigned r=0;V>1;++r)
  124.            {
  125.             unsigned Prime=Primes[r].prime[1],pow;
  126.             for(pow=0;!(V%Prime);++pow) V/=Prime;
  127.             Values[value].power[r]=pow;
  128.             if(Primes[r].count<pow) Primes[r].count=pow;
  129.            }
  130.          Values[value].have=true;
  131.         }
  132.      }
  133.    for(unsigned i=1;i<=500;++i)
  134.      {
  135.       if(Values[i].have)
  136.         {
  137.          list<unsigned> Result;
  138.          Result.push_back(1);
  139.          for(unsigned r=0;r<PrimeSize;++r)
  140.            {
  141.             unsigned pow=Primes[r].count-Values[i].power[r];
  142.             if(pow)
  143.               {
  144.                unsigned MulVal=Primes[r].prime[pow],move=0;
  145.                list<unsigned>::reverse_iterator ri=Result.rbegin();               
  146.                while(ri!=Result.rend())
  147.                  {
  148.                   move+=(*ri)*MulVal;
  149.                   unsigned next=move/1000000;
  150.                   *(ri++)=move-next*1000000;
  151.                   move=next;
  152.                  }
  153.                while(move)
  154.                  {
  155.                   unsigned next=move/1000000;
  156.                   Result.push_front(move-next*1000000);
  157.                   move=next;
  158.                  }
  159.               }
  160.            }
  161.          stringstream ss;
  162.          list<unsigned>::iterator ri=Result.begin();
  163.          ss<<*(ri++);
  164.          while(ri!=Result.end()) ss<<setw(6)<<setfill('0')<<*(ri++);
  165.          Values[i].result=ss.str();
  166.         }
  167.      }
  168.    for(unsigned i=0;i<N;++i) cout<<Values[T[i]].result<<endl;
  169.    return 0;
  170.   }
Success #stdin #stdout 0s 3868KB
comments (?)
stdin 
4
2
3
2
6
stdout 
3
2
3
1
https://ideone.com/W0zNCI
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!