ISS - Editorial

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 :wink:

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. :slight_smile:

11 Likes

I think my solution is exactly same as the tester.

4 Likes

Almost the same as my approach, but infact you can get a formula for f(N) in terms of it’s canonical representation.
Infact if N = p_1^{e_1}\cdots p_r^{e_r} then f(N) = N\prod_{i=1}^{r}\left(\frac{(e_i+1)(p_i-1)+1}{p_i}\right) which follows from some number theory(i.e. from the multiplicativity of the arithmetic function f). Now to compute the canonical factorisation fast we can precompute spf and that gives the fast solution. Did the tester do the same? I haven’t seen…

2 Likes

so 1.5k+ Div3 participants were able to solve this, interesting!

18 Likes

I also think my solution is the same as the tester’s solution.

for pythonistas this approach gives tle. There is a library called numba which boosts the computation speeds of phi, and F(n) s. Here is my code.

Thanks to @anon64527477.

4 Likes

Yeah its Big Brain Time :smile:

2 Likes

link to my code, similar approach but simplification is little different.

This was a very cool problem, can anyone suggest me some more problems on such gcd manipulations

3 Likes

[GCDEXTREME](SPOJ.com - Problem GCDEX

LCMSUM

3 Likes

S=∑​gcd(2∗i+1,4∗k+1)
This summation could also be looked as taking only odd multiples of factors d, since the total numbers with factor gcd d with 4k + 1 is ϕ(4k + 1 / d). The odd multiples would be just ceil(ϕ(4*k + 1 / d) + 1) / 2. Also, since, the sum starts from 3 (not one), so that needs to be handled when taking contribution of 1 in the sum.

1 Like

Are you sure?
Coz, after looking at your code I feel you misunderstood the reason for TLE. The reason could have been not using Fast IO too.

:rofl::rofl::joy::joy:

Yes @suman_18733097 ,
I’ve tested it, slow i/o is not the case here. It is negligible compared to the cost of these computations as there are very large numbers involved. Just try removing jit decorator and see the results. It takes around 20 secs to compute that function without jit decorator.

Even Div3 participants doing this much of maths is doubtful, Solving has a different place :sweat_smile:

ISL 2004 N2- https://artofproblemsolving.com/community/c6h30906p191396
My solution was still too slow though (CodeChef: Practical coding for everyone), didn’t know how to optimize it any further

Mind boggling Ques. and Nice Editorial , freshed up mind on solving & understanding this problem . :heart_eyes:

1 Like

Can anyone explain me the logic?

Since 2i+1 is odd so , 2i+1 is not divisible by 2 , which implies it is not divisible by 4 , so he just multiplied 4 in an expression , and it doesn’t affect GCD , since 2i+1 is not divisible by 4

2 Likes

S= ∑gcd(2∗i+1, 4∗k+1+(2∗i+1)∗(2∗i−1))
Using Euclid’s theorem again, we get S = ∑gcd(2∗i+1, 4∗k+1)

Didn’t understand this part