- #include <bits/stdc++.h>
- using namespace std;
- #define ll unsigned long long int
- #define N 5000010
- ll ph[N];
- void phi(){
- ph[1] = 0;
- for(int i = 2; i <N; i++) if(!ph[i]){
- for(int j = i; j <N; j+= i){
- if(!ph[j]) ph[j] = j;
- ph[j] = (ph[j]*(i-1))/i;
- }
- }
- for(int i=2;i<N;i++){
- ph[i]*=ph[i];
- ph[i]+=ph[i-1];
- }
- }
- int main(){
- phi();
- int ts;
- cin>>ts;
- for(int k = 1; k <= ts; k++){
- int a, b, c;
- scanf("%d%d", &a, &b);
- printf("Case %d: %llu\n", k, ph[b]-ph[a-1]);
- //cout<<"Case "<<k<<": <<ph[b]-ph[a-1]<<endl;
- }
- return 0;
- }
Thursday 27 July 2017
Lightoj 1007 - Mathematically Hard
Subscribe to:
Post Comments (Atom)
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...
-
Problem link: Problem Analysis: It is actually a basic Bisection problem , as we can see here we can not actually find a formula fo...
-
http://lightoj.com/volume_showproblem.php?problem=1382 Problem analysis: This is a rare problem i wrote about so far. After much strugg...
No comments:
Post a Comment