Coprime Array - HackerEarth Solution

Coprime Array  - HackerEarth Solution

Coprime Array  - HackerEarth Solution

You are given an array A of size N. A pair in the array A is a coprime if the \(gcd(A[i],A[j]) = 1\) where i and j are two indices and \( i \le (j-1)\). You need to return the sum of the product of every coprime pair i.e.
\(\sum_{i=1}^{n}\) \(\sum_{j=i+1}^{n} (A[i]*A[j]) \) where \(A[i],A[j] \) are coprime.

Input
First line contains T number of test cases.
For each test case, the first line contains the size of the array N followed by the array in the next line.

Output
For each testcase, Print the result mod 1000000007 in a new line

Constraints
\(1 \le T \le 5 \)
\(2 \le N \le 1000 \)
\( 1 \le A[i] \le 1000000 \)

Sample Input

1
3
1 2 3

Sample Output

11

Sample Explanation

In the given array, \((1,2)\) is copime so the product is 2, \((1,3)\) is coprime so the product is 3, \((2,3)\) is coprime so the product is 6. Adding them all gives 11%1000000007 = 11.

Coprime Array - HackerEarth Solution

Code:

#include<iostream>
using namespace std;

#define lld long long
#define MAX 1005
#define MOD 1000000007
int a[MAX];

lld gcd(lld a,lld b) {
  if(b == 0)
      return a;
  return gcd(b,a%b);
}

int main() {


  int t;
  cin>>t;

  while(t--) {

    int n;
    cin>>n;
    for(int i = 0;i<n;i++) 
        cin>>a[i];

    lld result = 0;

    for(int i = 0;i<n;i++) {
      for(int j = i+1;j<n;j++) {
        if(gcd(a[i],a[j]) == 1)
            result = (0ll + result + ((1ll * a[i]*a[j])%MOD))%MOD;
      }
    }

    cout<<result<<endl;
  }

  return 0;
}

Coprime Array - HackerEarth Solution

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the coderinme.net@gmail.com.

Disclaimer: The above Problem is generated by HackerEarth but the Solution is Provided by Us. This tutorial is only for Educational and Learning purposes. Authority if any of the queries regarding this post or website contact us on coderinme.net@gmail.com .

For DMCA: https://allhackerranksolutionsbykaira.blogspot.com/p/dmca.html