Spoj NAJPWG - Playing with GCD Solution

  Solution in C++: 

///**********ALLAH IS ALMIGHTY************///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh  

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define m 100009
4. long long result[m],i,j,d,k,v,r,n;
5. void phi()
6. {
7. result[0]=0;
8. for(k=1;k<=m;k++)
9. {
10. v=k;
11. r=v;
12. for(i=2;i*i<=v;i++)
13. {
14. if(v%i==0)
15. r-=r/i;
16. while(v%i==0)
17. v/=i;
18. }
19. if(v>1)
20. r-=r/v;
21. d=k-r;
22. result[k]=result[k-1]+d;
23. }
24.  
25. }
26. int main()
27. {
28. int t,n,i;
29. phi();
30. cin>>t;
31. for(i=1;i<=t;i++)
32. {
33. cin>>n;
34. printf("Case %d: %d\n",i,result[n]);
35. }
36. }