Count of pairs upto N such whose LCM is not equal to their product for Q queries | C ++ program to find the count of pairs from 1 to N such that their LCM is not equal to their product ; To store Euler 's Totient Function ; To store prefix sum table ; Compute Totients of all numbers smaller than or equal to N ; Make phi [ 1 ] = 0 since 1 cannot form any pair ; Initialise all remaining phi [ ] with i ; Compute remaining phi ; If phi [ p ] is not computed already , then number p is prime ; phi of prime number is p - 1 ; Update phi of all multiples of p ; Add the contribution of p to its multiple i by multiplying it with ( 1 - 1 / p ) ; Function to store prefix sum table ; Prefix Sum of all Euler 's Totient Values ; Total number of pairs that can be formed ; Driver Code ; Function call to compute all phi ; Function call to store all prefix sum
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE int phi [ N ] ; int pref [ N ] ; void precompute ( ) { phi [ 1 ] = 0 ; for ( int i = 2 ; i < N ; i ++ ) phi [ i ] = i ; for ( int p = 2 ; p < N ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( int i = 2 * p ; i < N ; i += p ) { phi [ i ] = ( phi [ i ] / p ) * ( p - 1 ) ; } } } } void prefix ( ) { for ( int i = 1 ; i < N ; i ++ ) pref [ i ] = pref [ i - 1 ] + phi [ i ] ; } void find_pairs ( int n ) { int total = ( n * ( n - 1 ) ) / 2 ; int ans = total - pref [ n ] ; cout << " Number ▁ of ▁ pairs ▁ from ▁ 1 ▁ to ▁ " << n << " ▁ are ▁ " << ans << endl ; } int main ( ) { precompute ( ) ; prefix ( ) ; int q [ ] = { 5 , 7 } ; int n = sizeof ( q ) / sizeof ( q [ 0 ] ) ; for ( int i = 0 ; i < n ; i ++ ) { find_pairs ( q [ i ] ) ; } return 0 ; }