PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Karanjeet Talwar
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Maths, Sieve of Eratosthenes, Euler Totient function
PROBLEM
Given a fixed integer k, We define an integer sequence A, where A_i = k+i*i. Now, we are tasked with computing the value \displaystyle \sum_{i = 1}^{2k} gcd(A_i, A_{i+1}).
There are Q queries, and for each query, an integer k is given.
QUICK EXPLANATION
- The summation is equivalent to \displaystyle \sum_{i = 1}^{2*K} gcd(2*i+1, 4*K+1) which is sum of gcd of all numbers from 3 to 4*K+1 with 4*K+1
- The required sum is \displaystyle X - 1 - \frac{X-(4*K+1)}{2} where \displaystyle X = \sum_{i = 1}^{4*K+1} gcd(i, 4*K+1) which can be computed for all K before processing test cases.
EXPLANATION
Let us do some math first.
We need \displaystyle S = \sum_{i = 1}^{2*k} gcd(k+i^2, k+(i+1)^2) = \sum_{i = 1}^{2*k} gcd(k+i*i, k+i*i+2*i+1)
We know from Euclid’s theorem that gcd(a, b) = gcd(a-b, b), so we can write \displaystyle S = \sum_{i = 1}^{2*k} gcd(2*i+1, k+i*i). Since 2*i+1 is odd, we can see that gcd(2*i+1, k+i*i) = gcd(2*i+1, 4*(k+i*i))
Hence, \displaystyle S = \sum_{i = 1}^{2*k} gcd(2*i+1, 4*k+4*i*i) = \sum_{i = 1}^{2*k} gcd(2*i+1, 4*k+1 +(4*i*i-1))
\displaystyle S = \sum_{i= 1}^{2*k} gcd(2*i+1, 4*k+1 + (2*i+1)*(2*i-1))
Using Euclid’s theorem again, we get \displaystyle S = \sum_{i= 1}^{2*k} gcd(2*i+1, 4*k+1)
Interpreting above summation, the required sum is the sum of gcd of all odd numbers from 3 to 4*k+1 with 4*k+1
For subtask 1, we can iterate over all odd numbers up to 4*k+1 for each query and compute the required sum.
Now, this part forward assumes understanding of euler totient function, \phi(n) denoting the number of natural numbers up to n which are coprime to n.
Ignoring odd constraint, can we compute sum of gcd of all values from 1 to N with N? The crucial observation is that in \displaystyle \sum_{i = 1}^N gcd(i, N), each term is a factor of N. We just need to count the number of times each factor d appears in the summation. Say gcd(x, N) = d, so gcd(x/d, N/d) = 1. We just need the number of values x/d, which are co-prime with N/d, which is given by \phi(N/d).
Hence, We can write \displaystyle \sum_{i = 1}^N gcd(i, N) = \sum_{d|N} d * \phi(N/d). This is explained in detail here. Let’s denote \displaystyle f(N) = \sum_{i = 1}^N gcd(i, N)
Returning to the odd numbers constraint, let’s try computing gcd of all numbers upto 4*K+1 with 4*K+1 and then subtracting the sum of gcd of all even numbers up to 4*K+1 with 4*K+1.
We get \displaystyle S = f(4*K+1)-1 - \sum_{i = 1}^{2*K} gcd(2*i, 4*K+1). Denoting \displaystyle E = \sum_{i = 1}^{2*K} gcd(2*i, 4*K+1). Since 4*K+1 is odd, gcd(2*i, 4*K+1) = gcd(i, 4*K+1)
\displaystyle E = \sum_{i = 1}^{2*K} gcd(i, 4*K+1) = \sum_{i = 1}^{2*K} gcd(i, 4*K+1-i) = \sum_{i = 1}^{2*K} gcd(4*K+1, 4*K+1-i)
This way, we proved that f(4*K+1) = \displaystyle \sum_{i = 1}^{4*K+1} gcd(i, 4*K+1) = 2*E + 4*K+1 \implies E = (f(4*K+1)-4*K+1)/2
Hence, we have \displaystyle S = f(4*K+1)-1 - \frac{f(4*K+1)-(4*K+1)}{2}
So, if we can compute f(N) quickly, we have solved this problem. f(N) can be easily computed in sieve style before processing test cases for all possible 4*K+1.
Looking for a challenge
Try to prove why tester’s solution works 
Hint
Inclusion Exclusion
Notes
- I saw several people posting in problems page getting TLE with O(log(N)) solutions. Most of the times, they were using slow input output, using endl. There are 10^6 integers read and printed, so slow IO is not an option.
- Secondly, some people declared array sizes 4*10^6+1 where they needed 4*10^6+2, failing their program on input k = 10^6
TIME COMPLEXITY
The time complexity is O(K_{max}*log(K_{max}) + T) where K_{max} = 10^6
SOLUTIONS
Setter's Solution
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define flash ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
int euler[4000002];int ans[4000002];
void pre()
{
euler[0]=0;
for(ll i=1;i<=4000001;i++)
euler[i]=i;
for(ll j=2;j<=4000001;j++)
{
if(euler[j]==j)
{
for(ll k=j;k<=4000001;k+=j)
euler[k]-=euler[k]/j;
}
}
for(ll j=1;j<=4000001;j++)
{
for(ll k=j;k<=4000001;k+=j)
{
ans[k]+=j*euler[k/j];
}
}
}
int main()
{
pre();
flash
ll t;
cin>>t;
while(t--)
{
ll k=0;
cin>>k;
ll boom=ans[4*k+1]-1-4*k;
boom=boom/2;
boom-=ans[4*k+1];
boom=boom*-1;
boom--;
cout<<boom<<"\n";
}
}
Tester's Solution
import java.util.*;
import java.io.*;
class ISS{
//SOLUTION BEGIN
int MX = (int)1e6;
int[] spf, mobius;
long[] ans;
void pre() throws Exception{
ans = new long[1+MX];
spf = spf(4*MX+1);
mobius = mobius(spf, 4*MX+1);
for(int k = 1; k <= MX; k++){
int[] fact = factors(spf, 4*k+1);
Arrays.sort(fact);
int[] count = new int[fact.length];
long sum = 0;
for(int i = fact.length-1; i>= 0; i--){
count[i] = ((4*k+1)/fact[i]+1)/2;
for(int j = i+1; j< fact.length; j++){
if(fact[j]%fact[i] == 0)
count[i] -= count[j];
}
sum += fact[i]*(long)count[i];
}
ans[k] = sum-1;
}
}
void solve(int TC) throws Exception{
pn(ans[ni()]);
}
int gcd(int x, int y){return y == 0?x:gcd(y, x%y);}
void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
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;
}
int[] mobius(int[] spf, int max){
int[] mob = new int[1+max];
mob[1] = 1;
for(int i = 2; i<= max; i++)
if(spf[i/spf[i]] != spf[i])
mob[i] = -mob[i/spf[i]];
return mob;
}
int[] factors(int[] spf, int x){
int[] factor = new int[]{1};
while(x > 1){
int p = spf[x], cnt = 0;
for(;x%p == 0; x/= p)cnt++;
int[] tmp = Arrays.copyOf(factor, (1+cnt)*factor.length);
for(int pw = 1, cur = p; pw <= cnt; pw++, cur *= p)
for(int i = 0; i< factor.length; i++)
tmp[pw*factor.length+i] = factor[i]*cur;
factor = tmp;
}
return factor;
}
//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 ISS().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. 
