Skip to main content

CodeChef --- GCD operations


 First check the number is prime or not using sieve-of-eratosthenes(https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)

CASE 1 == if the number is prime then the number is equal to i or not
CASE 2 == in the case of not prime the given and i is equal to given number or not
          Example:in the second case of the problem for the fourth position given number is 2 & i=4 gcd of (2,4)=2 so that is true
                  in the first case of the problem for the third position given number is 2 & i=3 gcdof (2,3)=1 & given in array is 2 so that is false

///Bismillahir Rahmanir Rahim
///Author: Tanvir Ahmmad
///CSE,Islamic University,Bangladesh

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<iterator>
#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array
/*every external angle sum=360 degree
  angle find using polygon hand(n) ((n-2)*180)/n*/
///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b
using namespace std;
typedef long long ll;
#define sz 100002

bool vis[100002]={true};

void seive()
{
    for(int i=2;i<=sz;i+=2) vis[i]=false;
    for(int i=3;i<=sz;i+=2)
        if(vis[i]==true)
            for(ll j=i*i;j<=sz;j+=i) vis[j]=false;
    vis[1]=false;
}

int main()
{
    seive();
    ll tst,n;
    cin>>tst;
    while(tst--)
    {
        cin>>n;
        ll arr[n+2],flag=0;
        for(ll i=1;i<=n;i++) cin>>arr[i];
        for(ll i=2;i<=n;i++)
        {
            if(arr[i]!=i)
            {
                if(vis[i]==true)
                {
                    flag=1;
                    break;
                }
                if(arr[i]!=__gcd(i,arr[i]))
                {
                    flag=1;
                    break;
                }
            }

        }
        if(flag==1) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}
///Alhamdulillah

problem link:https://www.codechef.com/LP2TO307/problems/GCDOPS
Labels:

Comments

Post a Comment

Popular posts from this blog

Codeforces round 1676(A. Lucky?)

Just count the  first three  &  last three  number ///Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int>()) for decrement of array /*every external angle sum=360 degree   angle find using polygon hand(n) ((n-2)*180)/n*/ ///Floor[Log(b)  N] + 1 = the number of digits when any number is repres...
Post a Comment
Read more

Maximum Number of Coins You Can Get (LeetCode)

Problem Name: 1561.  Maximum Number of Coins You Can Get Problem Link: https://leetcode.com/problems/maximum-number-of-coins-you-can-get/description/ Difficulty: Medium Tag: Sorting | Array | Math | Greedy | Sorting | Game theory Language: C# | C++ OJ: LeetCode Algorithm: Sort the Piles: Sort the array of piles in descending order, so that the piles with the maximum number of coins are at the beginning. Calculate the Total Number of Piles to Collect From: Determine the total number of piles you can collect coins from based on the rule that for every three consecutive piles, you can only pick coins from two of them. Set this value to 2/3 of the total number of piles. Iterate Through Piles and Collect Coins: Start iterating through the sorted piles from the second pile (index 1) and continue up to the calculated total number of piles to collect from. In each iteration, collect the coins from the current pile. Since you can only collect coins from every second pile, use a step of ...
Post a Comment
Read more

Codeforces round 1661(B. Getting Zero)

using   second operation  the answer is maximum is  15  because  2 15 =32768 so we need to  pre-calculate all the illegible input 0 to 32768   using  second operation Then  just increment 1(using first operation)  from input check is it  minimum is not ! ///Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int...
Post a Comment
Read more