0
Your rating: None

CodeChef submission 136801 (C++ 4.0.0-8)

CodeChef submission 136801 (C++ 4.0.0-8) plaintext list. Status: WA, problem SNCK04, contest SNACKDWN. By code4life (code4life), 2009-11-21 23:58:57.
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <stack>
  7. #include <bitset>
  8. #include <algorithm>
  9. #include <functional>
  10. #include <numeric>
  11. #include <utility>
  12. #include <sstream>
  13. #include <iostream>
  14. #include <iomanip>
  15. #include <cstdio>
  16. #include <cmath>
  17. #include <cstdlib>
  18. #include <ctime>
  19. #include<string>
  20. #define MAX 1000001
  21. #define eps 1e-6
  22. using namespace std;
  23. string i2s(int n)
  24. {  stringstream ss;
  25.    ss<<n;
  26.    return ss.str();  
  27. }
  28. int s2i(string h)
  29. {   stringstream ss;
  30.     ss<<h;
  31.     int n;
  32.     ss>>n;
  33.     return  n;
  34. } 
  35. long long array[1000000];long long array1[1000000];
  36. int main()
  37. {   vector<int> prime;prime.clear();prime.push_back(2);int count=0;
  38.     for(int i=3;i<=1000;i=i+2)
  39.     {   set<int> s;s.clear();
  40.         double r=sqrt(i);
  41.         for(int j=1;j<=floor(r);j++)
  42.         {   if(i%j==0)
  43.             {  s.insert(j);
  44.                s.insert(i/j);
  45.             }
  46.         }
  47.         if(s.size()==2)
  48.         {   prime.push_back(i);
  49.             count++;
  50.         }
  51.     } 
  52.     memset(array,0,sizeof(array));memset(array1,0,sizeof(array1));
  53.     array[0]=0;array[1]=1;array1[0]=0;array1[1]=1;
  54.     for(int i=3;i<=1000000;i++)
  55.     {   int p=i;int l=(int)sqrt(i);bool flag=false;
  56.         for(int j=0;j<prime.size() && prime[j]<=l;j++)
  57.         {   if(p%prime[j]==0)
  58.             {   array[i-1]=((array[(p/prime[j])-1]*i)/(p/prime[j]));flag=true;
  59.                 break;
  60.             }
  61.         }
  62.         if(!flag)
  63.         {  // case of prime value
  64.            array[i-1]=(i-1);
  65.         }
  66.         array1[i-1]=array1[i-2]+(array[i-1]);
  67.     }      
  68.     int t;scanf("%d",&t);
  69.     while(t--)
  70.     {  int num;scanf("%d",&num);//cout<<array[num-1]<<endl;
  71.        cout<<array[num-1]<<endl;
  72.     }
  73.     system("pause");
  74. }   
  75.

Comments