akash2504's blog

By akash2504, 12 years ago, In English

http://www.spoj.pl/problems/MAIN12B/ i m trying this problem but getting wa i have tried for many test cases but still couldnt get through my approach is 1- generated primes upto 10^6 using sieve 2- for each prime i checked if it divides any of the given numbers (since numbers are small n<100) and replaced it by a[i]/p 3- i chacked if some of the numbers are left in the array(other then 1) since they are prime greater than 10^6

plz correct me if i m wrong somewhere.... :(

here is my code


#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 1000005 typedef long long LL; LL prime[MAX]; LL num[100000]; int main(){ LL l=0; LL i,j; for(i=0;i<MAX;i++) prime[i]=1; prime[0]=0; prime[1]=0; for(i=2;i*i<=MAX;i++){ if(prime[i]){ for(j=i*i;j<MAX;j+=i) prime[j]=0; } } for(i=2;i<MAX;i++) if(prime[i]) num[l++]=i; LL test; scanf("%lld",&test); LL o=1; while(o<=test){ LL a[105]; LL n; printf("Case #%lld: ",o); scanf("%lld",&n); for(i=0;i<n;i++) scanf("%lld",&a[i]); LL flag=1; LL gh[100000],f=0; for(i=0;i<l;i++){ LL k=num[i]; LL s=1; for(j=0;j<n;j++){ if(num[i]<a[j])flag=0; if(a[j]%k==0&&a[j]!=1){ if(s){ gh[f++]=k; s=0;} while(a[j]%k==0) a[j]/=k; } } if(flag==1)break; } for(i=0;i<n;i++) if(a[i]!=1&&a[i]>MAX) gh[f++]=a[i]; printf("%lld\n",f); for(i=0;i<f;i++) printf("%lld\n",gh[i]); o++; } return 0; }
  • Vote: I like it
  • -15
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just read statements carefully =) You must output an answer in non-decreasing order. But it is not guaranteed that a[i] are sorted in same way. In your solution you can add big primes to answer in random order. Simple test: {10^9+7; 2; 3}. For example, sort your array (after dividing elements by small primes). Think it could help.