0
Your rating: None

CodeChef submission 136791 (C++ 4.3.2)

CodeChef submission 136791 (C++ 4.3.2) plaintext list. Status: TLE, problem SNCK04, contest SNACKDWN. By sparta (sparta), 2009-11-21 23:57:42.
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<cctype>
  6. #include<algorithm>
  7. #include<map>
  8. #include<vector>
  9. #include<list>
  10. #include<set>
  11. #include<queue>
  12. #include<cassert>
  13. #include<fstream>
  14. #include<deque>
  15. #include<stack>
  16. #include<bitset>
  17. #include<sstream>
  18. #include<iomanip>
  19. #include<string>
  20. #include<cmath>
  21. #include<ctime>
  22. using namespace std;
  23. #define MAXLEN 1000001
  24. int arr[MAXLEN];
  25.  
  26. void pre()
  27. {
  28. 	 int save,mult,n,i;
  29. 	  for(n=1;n<MAXLEN;++n)
  30. 	  {
  31.         mult=n;
  32. 		save=n;
  33.         for(i=2;i*i<=n;++i)
  34. 		{
  35. 			if(n%i==0)
  36. 			{
  37.                mult-=mult/i;
  38. 			  while(n%i==0)n/=i;
  39. 			}
  40. 		}
  41. 		if(n>1) mult=mult-mult/n;
  42. 		n=save;
  43. 		arr[n]=mult;
  44. 	}
  45. }
  46. int main()
  47. {int tc,n,i;
  48. arr[0]=0;arr[1]=0;
  49.     pre();
  50. 	long long int v[MAXLEN];
  51. 	v[0]=0;v[1]=0;
  52. 	for(i=2;i<MAXLEN;++i)v[i]=v[i-1]+arr[i];
  53. 	scanf("%d",&tc);
  54. while(tc--)
  55. {
  56.  scanf("%d",&n);
  57. 	printf("%lld\n",v[n]);
  58. }
  59. }
  60.

Comments