guacamolesyrup's blog

GCD
By guacamolesyrup, history, 7 years ago, In English

Sabbir and GCDs I was trying this problem but somehow i am getting WA after 10th testcase. Can anyone give me some hints how to solve it?Thanks in advance.I have updated my solution now it is showing WA again.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define MAX 100009
#define MOD 1000000007
#define fast ios::sync_with_stdio(false);
#define INF 1000000000000000LL
#define INM -INF
#define pi 3.14159265358979323846264338327950

vector<int>prime;
bool isprime[1000011];

void sieve(){
	for(int i=2;i<=sqrt(1000010);i++){
		if(!isprime[i]){
			for(int j=i+i;j<=1000010;j+=i)
			isprime[j]=1;
		}
	}
	prime.pb(2);
	for(int i=3;i<=1000010;i+=2){
		if(!isprime[i])
		prime.pb(i);
	}
}
int main(){
	fast
	int t;
	sieve();
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int a[n];
		for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	    }
	    set<int>S;
		for(int i=0;i<n;i++){
			for(int j=0;j<prime.size()&& prime[j]*prime[j]<=a[i];j++){
				while(a[i]%prime[j]==0){
					S.insert(prime[j]);
					a[i]/=prime[j];
				}
			}
			if(a[i]>1){
				S.insert(a[i]);
			}
		}
		for(int i=0;i<prime.size();i++){
			if(S.find(prime[i])==S.end()){
				printf("%d\n",prime[i]);
				break;
			}
		}
	}
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just look for the smallest prime such that it is not the factor of any of the numbers?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    - #include<bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define MAX 100009
#define MOD 1000000007
#define fast ios::sync_with_stdio(false);
#define INF 1000000000000000LL
#define INM -INF
#define pi 3.14159265358979323846264338327950

vector<int>prime;
bool isprime[1000011];

void sieve(){
	for(int i=2;i<=sqrt(1000010);i++){
		if(!isprime[i]){
			for(int j=i+i;j<=1000010;j+=i)
			isprime[j]=1;
		}
	}
	prime.pb(2);
	for(int i=3;i<=1000010;i+=2){
		if(!isprime[i])
		prime.pb(i);
	}
}
int main(){
	fast
	int t;
	sieve();
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int a[n];
		for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
		for(int i=0;i<prime.size();i++){
			int flag=0;
			for(int j=0;j<n;j++){
				if(a[j]%prime[i]==0){
					flag=1;
					break;
				}
			}
			if(!flag){
				printf("%d\n",prime[i]);
				break;
			}
		}
	}
}

    I have implemented idea in above but now i am getting TLE.can you add some optimizations?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      instead of trying to find the prime factor by factoring the numbers, you can find the prime factor of a number in log after some preprocessing. Here's a link that might help.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is my AC solution. Hope it helps. spf[x] is the smallest prime factor of a number x. The idea here is to mark all the prime factors of all numbers efficiently and then print the smallest unmarked prime.


bool prime[N+5]; 
vector<int> primesVec;
void SieveOfEratosthenes(ll n) {
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for(ll p=2; p*p<=n; p++){ 
        if (prime[p] == true){
            for(ll i=p*p;i<=n;i+=p) 
            prime[i] = false; 
        } 
    } 
    for(ll p=2; p<=n; p++){
        if (prime[p]) {
            primesVec.push_back(p);
        }
    }
}

ll spf[N];
void SPF() { 
    spf[1] = 1; 
    // marking smallest prime factor for every number to be itself.
    for (ll i = 2; i < N; i++) spf[i] = i; 
  
    // separately marking spf for every even number as 2 
    for (ll i=4; i<N; i+=2) spf[i] = 2;
  
    for (ll i=3; i*i<N; i++) { 
        // checking if i is prime 
        if (spf[i] == i) { 
            // marking SPF for all numbers divisible by i 
            for (ll j=i*i; j<N; j+=i) 
                // marking spf[j] if it is not  
                // previously marked 
                if (spf[j]==j) spf[j] = i; 
        } 
    } 
}

int check[N];

void getFactorization(int x) { 
    while (x != 1) { 
        check[spf[x]] = 1;
        x = x / spf[x]; 
    }
} 

void solve() {
    ll x, y, z, k, sum = 0, d;
    memset(check, 0, sizeof check);

    cin >> n;
    f(i, n) {
        cin >> x;
        getFactorization(x);
    }

    for(int p: primesVec) {
        if(check[p] == 0) {
            cout << p << endl;
            return;
        }
    }
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks, He was waiting for the solution for the past 3 years.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      See I helped because I too visit old blogs and sometimes people do lord's job by posting valuable stuff about the problem which I like the most about codeforces blogs. The blog is not just for a single person rather its for the whole codeforces community.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it seems like the poster has been away from CF for nearly 2 years. :(

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, and that does not matter at all. There may be other people looking for the solution.

      Obligatory XKCD:

      → Reply