PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter:
Tester: Lavish Gupta and Abhinav Sharma
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
PROBLEM
Given two integers a and b, we define f(a, b) as the maximum value of |\gcd(a, x) - \gcd(b, x)| where x is some natural number. Formally,
f(a, b) = \max\limits_{x \in \mathbb{N}}| \gcd(a,x) - \gcd(b,x)|
(where \mathbb{N} represents the set of natural numbers and \gcd(a, b) represents the greatest common divisor of a and b)
You are given an integer k. You need to find the number of ordered pairs (a, b) such that f(a, b) = k.
QUICK EXPLANATION
- A pair (a, b) shall have f(a, b) = (max(a, b)/g-1) * g where g = gcd(a, b)
- The number of pairs with f(a, b) = k shall have
EXPLANATION
Rewriting f(a, b)
Let’s consider a pair (a, b) with a \lt b and try to compute f(a, b). We want to find the maximum difference between gcd(a, x) and gcd(b, x). Sinec 1 \leq gcd(p, q) \leq p, q for any positive integers p and q, the maximum difference we can achieve is b-1, wheren gcd(b, x) = b and gcd(a, x) = 1
But this can happen only when gcd(a, b) = 1. Hence, for pairs (a, b) where a and b are co-prime, f(a, b) = max(a, b)-1.
Let’s generalize. Considering a pair (a, b) such that gcd(a, b) = g, then we can see that f(a/g, b/g) = max(a, b)/g-1 and f(a, b) = g * f(a/g, b/g) = g * (max(a, b)/g-1) = max(a, b) - g.
Hence, we can write f(a, b) = max(a, b) - gcd(a, b).
Additional observation is that f(a, a) = a-a = 0, So they do not affect our answer. Hence, we can consider only unordered pairs (a, b) where a \lt b and then multiply the answer by 2. So, For the rest of the editorial, assume a \lt b.
The number of pairs with f(a, b) = K
We need number of pairs (a, b) where a \lt b such that b - gcd(a, b) = K. Assuming g = gcd(a, b), g must divide K as well.
Let’s substitute a = p*g and b = q*g. So we have q*g - g = K. We can see that p and q must be co-prime.
Hence, let’s iterate over all factors of K. If the current factor is g, we get q - 1 = K/g. So we must have q = 1+K/g. 1 \leq p \lt q and gcd(p, q) = 1. What is the number of values of p satisfying these conditions?
Let’s define function \phi(N) as the number of integers co-prime to N up to N. i.e. the number of integers x such that 1 \leq x \leq N and gcd(x, N) = 1.
Hence, for each factor g of K, we have \phi(K/g+1) choices of a and exactly one choice for b, contributing \phi(K/g+1) pairs to the number of pairs (a, b) with f(a, b) = K
The \phi(N) function
The \phi(N) function is well known as the Euler totient function, which can be computed beforehand for all integers from 1 to M = 10^6+1 in O(M*log(log(M))) time in sieve style, as explained in this article.
It is important to compute \phi(N) for 10^6+1 as well, as when we consider K = 1000000 and g = 1,we need \phi(1000001).
Following pseudocode represent precomputing all answers from 1 to M assuming \phi(N) is already calculated.
for g in 1 to M:
for k = g to M, step size g:
ans[k] += phi[k/g+1]
TIME COMPLEXITY
The time complexity of the above solution is O(M*log(M) + T), though the time limit was relaxed enough to allow certain T * \sqrt M kind of approaches to pass.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const int N = 1e6+5;
int phi[N], ans[N];
void precompute_phi()
{
phi[0] = 0;
phi[1] = 1;
for(int i = 2; 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;
}
}
}
void precompute_answer()
{
for(int i = 1; i < N; i++)
{
for(int j = i; j < N; j += i)
{
// i is a factor of j
ans[j] += 2 * phi[i + 1];
}
}
}
int32_t main()
{
IOS;
precompute_phi();
precompute_answer();
int T; cin >> T;
while(T--)
{
int k; cin >> k;
cout << ans[k] << endl;
}
return 0;
}
Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
assert('a'<=g and g<='z');
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1000000;
const int MAX_N = 1000000 ;
#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_len = 0;
int max_n = 0;
int max_k = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
int max_s = 0 ;
int n;
vector<int> factors[MAX_N+1] ;
vector<int> euler(MAX_N + 10) ;
void pre()
{
for(int i = 1 ; i <= MAX_N+1 ; i++)
euler[i] = i ;
for(int i = 1 ; i <= MAX_N ; i++)
{
for(int j = i ; j <= MAX_N ; j += i)
{
factors[j].push_back(i) ;
}
if(factors[i].size() == 2)
{
for(int j = i ; j <= MAX_N+1 ; j += i)
{
euler[j] = (euler[j]/i)*(i-1) ;
}
}
}
return ;
}
void solve()
{
n = readIntLn(1 , MAX_N) ;
ll ans = 0 ;
for(int i = 0 ; i < factors[n].size() ; i++)
{
ll g = factors[n][i] ;
ll ad = (n+g)/g ;
ans += euler[ad] ;
}
ans *= 2 ;
cout << ans << '\n' ;
return ;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.txt", "r" , stdin);
freopen("outputf.txt", "w" , stdout);
#endif
// fast;
int t = 1;
t = readIntLn(1,MAX_T);
pre() ;
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"maxN : " << max_n << '\n';
// cerr<<"maxK : " << max_k << '\n';
// cerr<<"Sum of lengths : " << sum_len << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Tester's Solution 2
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e6;
const int MAX_N = 1e6+5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
int n;
vector<long long> ans(MAX_N);
vector<int> phi(MAX_N);
void pre(){
phi[0]=0;
phi[1]=1;
for(int i = 2; i <= MAX_N; i++)
phi[i] = i;
for(int i = 2; i <= MAX_N; i++){
if(phi[i] == i){
for (int j = i; j <= MAX_N; j += i)
phi[j] -= phi[j] / i;
}
}
for(int i=1; i<MAX_N ; i++){
for(int j = i; j<MAX_N; j+=i){
ans[j] += phi[i+1];
}
}
}
void solve()
{
n = readIntLn(1, 1e6);
sum_len += n;
int res = 0;
for(int i=1; i*i<=n; i++){
if(n%i==0){
res += phi[i+1];
if(i*i!=n) res+=phi[n/i+1];
}
}
cout<<2*res<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
pre();
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_len << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class MAXGCDVAL{
//SOLUTION BEGIN
int MX = (int)1000000;
int[] ans;
void pre() throws Exception{
int[] spf = spf(1+MX), phi = phi(spf, 1+MX); ans = new int[1+MX];
for(int p = 1; p <= MX; p++)
for(int q = p; q <= MX; q+= p)
ans[q] += phi[q/p+1];
}
void solve(int TC) throws Exception{
pn(2*ans[ni()]);
}
//euler phi function
int[] phi(int[] spf, int max){
int[] phi = new int[1+max];
phi[1] = 1;
for(int i = 2; i <= max; i++){
int r = i/spf[i];
if(spf[r] == spf[i])phi[i] = phi[r]*spf[i];
else phi[i] = phi[r]*(spf[i]-1);
}
return phi;
}
int[] spf(int max){
int[] spf = new int[1+max];
for(int i = 2; i<= max; i++)
if(spf[i] == 0)
for(int j = i; j <= max; j += i)
if(spf[j] == 0)
spf[j] = i;
return spf;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MAXGCDVAL().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 