Thursday 27 July 2017

Lightoj 1007 - Mathematically Hard


  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll unsigned long long int
  4. #define N 5000010
  5. ll ph[N];
  6. void phi(){
  7.     ph[1] = 0;
  8.     for(int i = 2; i <N; i++) if(!ph[i]){
  9.         for(int j  = i; j <N; j+= i){
  10.             if(!ph[j]) ph[j] = j;
  11.             ph[j] = (ph[j]*(i-1))/i;
  12.         }
  13.     }
  14.     for(int i=2;i<N;i++){
  15.             ph[i]*=ph[i];
  16.             ph[i]+=ph[i-1];
  17.     }
  18. }
  19. int main(){
  20.     phi();
  21.     int ts;
  22.     cin>>ts;
  23.     for(int k = 1; k <= ts; k++){
  24.         int a, b, c;
  25.         scanf("%d%d"&a, &b);
  26.         printf("Case %d: %llu\n", k, ph[b]-ph[a-1]);
  27.         //cout<<"Case "<<k<<": <<ph[b]-ph[a-1]<<endl;
  28.     }
  29.     return 0;
  30. }

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...