Saleh127

e-olym 1147

Sep 9th, 2020
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; while(t--)
  5. ll phi[200008],sum[200005];
  6. ll a,c,d,e,f,i,j,k,l;
  7. void phiii()
  8. {
  9. for(i=1;i<=200005;i++)
  10. {
  11. phi[i]=i;
  12. }
  13. for(i=2;i<=200005;i++)
  14. {
  15. if(phi[i]==i)
  16. {
  17. phi[i]=i-1;
  18. for(j=2*i;j<=200005;j+=i)
  19. {
  20. phi[j]=(phi[j]/i)*(i-1);
  21. }
  22. }
  23. }
  24. }
  25.  
  26. void summm()
  27. {
  28. phiii();
  29. for(i=1;i<200005;i++)
  30. {
  31. for(j=2;i*j<200005;j++)
  32. {
  33. sum[i*j]+=(i*phi[j]);
  34. }
  35. }
  36. for(i=2;i<200005;i++)
  37. {
  38. sum[i]+=sum[i-1];
  39. }
  40. }
  41.  
  42. int main()
  43. {
  44. ios_base::sync_with_stdio(0);
  45. cin.tie(0);cout.tie(0);
  46.  
  47. summm();
  48. while(cin>>a &&a)
  49. {
  50. cout<<sum[a]<<endl;
  51. }
  52.  
  53. return 0;
  54. }
  55.  
Advertisement
Add Comment
Please, Sign In to add comment