SUMMATION - Editorial

PROBLEM LINK:

Practice

Author: Siddharth Jha
Tester: Siddharth Jha
Editorialist: Siddharth Jha

DIFFICULTY:

EASY

PREREQUISITES:

Euler Totient Function, Prefix Sums

PROBLEM:

Numbers X and Y are considered interesting if GCD(X,Y) = 1, A function f(n) is defined as count of all numbers X from 1 to N such that X and N are interesting.
Given A,B find f(A) + f(A+1) + f(A+2) ... f(B).

QUICK EXPLANATION:

Totient function of a number N is the count of numbers from 1 to N such that Gcd(i,N) = 1 or they are co-prime of N. It can be efficiently calculated in O(NloglogN) using the idea of Sieve.

Toteint Function Snippet

void phi_1_to_n(int n) {
vector phi(n + 1);
for (int i = 0; i <= n; i++)
phi[i] = i;

for (int i = 2; i <= n; i++) {
    if (phi[i] == i) {
        for (int j = i; j <= n; j += i)
            phi[j] -= phi[j] / i;
    }
}

}

After calculating this as there are 10^5 Test cases the overall complexity will be O(TNloglogN) 10^8. Therefore we need to optimize it.

Hint

Use Prefix sum to answer each query of A to B, Pre-calculate Prefix sum for each number. Which will answer quries in O(1). Hence Finally Time complexity will be O(T + NloglogN + N)

SOLUTIONS:

Setter's Solution

//Siddharth Jha

#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<ll, null_type, less, rb_tree_tag, tree_order_statistics_node_update> pbds;
//typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> pbtrie;

#define ll long long int
#define mod 1000000007
#define inf 1e18
#define pb push_back
#define vi vector
#define vs vector
#define pii pair<ll,ll>
#define ump unordered_map
#define mp make_pair
#define pq_max priority_queue
#define pq_min priority_queue<ll,vi,greater >
#define all(n) n.begin(),n.end()
#define ff first
#define ss second
#define mid(l,r) (l+(r-l)/2)
#define bitc(n) __builtin_popcount(n)
#define SET(a) memset( a, -1, sizeof a )
#define CLR(a) memset( a, 0, sizeof a )
#define Pi 3.141592653589793
#define loop(i,a,b) for(int i=(a);i<=(b);i++)
#define looprev(i,a,b) for(int i=(a);i>=(b);i–)
#define _fast ios_base::sync_with_stdio(0); cin.tie(0);
#define iter(container,it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define log(args…) {string _s = #args; replace(_s.begin(), _s.end(), ‘,’, ’ '); stringstream _ss(_s); istream_iterator _it(_ss); err(_it, args); }
#define logarr(arr,a,b) for(int z=(a);z<=(b);z++) cout<<(arr[z])<<" ";cout<<endl;
template T gcd(T a, T b){if(a%b) return gcd(b,a%b);return b;}
template T lcm(T a, T b){return (a*(b/gcd(a,b)));}
vs tokenizer(string str,char ch) {std::istringstream var((str)); vs v; string t; while(getline((var), t, (ch))) {v.pb(t);} return v;}

void err(istream_iterator it) {}
template<typename T, typename… Args>
void err(istream_iterator it, T a, Args… args) {
cout << *it << " = " << a << endl;
err(++it, args…);
}

ll mx = 1e7+5;
vi phi(mx),presum(mx);
void precompute() {
loop (i,0,mx-1)
phi[i] = i;

loop (i,2,mx-1) {
    if (phi[i] == i) {
        for (int j = i; j <= mx; j += i)
            phi[j] -= phi[j] / i;
    }
}

loop (i,1,mx-1) {
    presum[i] = presum[i-1] + phi[i];
}

}

void solve() {
ll a,b; cin >> a >> b;
cout << presum[b] - presum[a-1] << “\n”;
}

int main(int argc, char const *argv[]){
_fast
//#ifndef ONLINE_JUDGE
//freopen(“input.txt”, “r”, stdin);
//freopen(“output.txt”, “w”, stdout);
//#endif
ll t; cin>>t;
precompute();
while(t–){
solve();
}
return 0;
}