Advertisement
Saleh127

UVA 10990

Nov 5th, 2020
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. #define maX 2000008
  6.  
  7. bool marked[maX];
  8. ll ans[maX];
  9. ll phi[maX];
  10.  
  11. void sieve()
  12. {
  13. marked[0]=1;
  14. marked[1]=1;
  15. for(ll i=4;i<=maX;i+=2)
  16. {
  17. marked[i]=1;
  18. }
  19. for(ll i=3;i<=maX;i+=2)
  20. {
  21. if(marked[i]==0)
  22. {
  23. for(ll j=i*i; j<=maX; j+=i+i)
  24. {
  25. marked[j]=1;
  26. }
  27. }
  28. }
  29. }
  30.  
  31. void phifunc()
  32. {
  33. ll i,j;
  34. for(i=1;i<=maX;i++)
  35. {
  36. phi[i] = i;
  37. }
  38.  
  39. for(i=2;i<=maX;i++)
  40. {
  41. if(marked[i] == 0)
  42. {
  43. for(j=i;j<=maX;j+=i)
  44. {
  45. phi[j] = phi[j]/i*(i-1);
  46. }
  47. }
  48. }
  49. }
  50.  
  51. void sodf()
  52. {
  53. ll i,j,k,n;
  54. ans[1]=0;
  55. for(i=2;i<=maX;i++)
  56. {
  57. n=i;
  58. j=0;
  59. while(n!=1)
  60. {
  61. n=phi[n];
  62. j++;
  63. }
  64. ans[i]=j;
  65. }
  66. }
  67.  
  68. int main()
  69. {
  70. ios_base::sync_with_stdio(0);
  71. cin.tie(0);cout.tie(0);
  72.  
  73. sieve();
  74. phifunc();
  75. sodf();
  76.  
  77.  
  78. ll a,b,c,i,j,k,l;
  79. test
  80. {
  81. cin>>a>>b;
  82. c=0;
  83. for(i=a;i<=b;i++)
  84. {
  85. c+=ans[i];
  86. }
  87. cout<<c<<endl;
  88. }
  89.  
  90.  
  91. return 0;
  92. }
  93.  
Advertisement
RAW Paste Data Copied
Advertisement