SGARDEN WA

general
,
1

I have used the method given in the editorial. I am repeatedly getting WA. Can somebody point out the mistake?

Code:

 
#include
#define si(a) scanf("%d",&a)
#define M 1000000007 
#define ULL unsigned long long

using namespace std;

int primes[100001];
int prm[9592];
int mul[100001];


void generate(void)
{
  int i,j;
  for(i=2;i<=100000;i++)primes[i]=1;
  primes[0]=0;
  primes[1]=0;
  for(i=2;i<=100000;i++){
    if(primes[i]==1){
       for(j=2;i*j<=100000;j++)primes[i*j]=0;                                 
    }                            
  }
	j=0;
  for(i=2;i<=100000;i++){
  	if(primes[i]==1){
  		prm[j]=i;
  		j++;
  	}		
  } 
}

int Arr[100001],V[100001];


int pwr[9592]={0};

ULL powr(ULL a,ULL n)
{  
    ULL ans=a,p=0,q=0,k;
    if(n==0)return 1;
    if(n==1)return a;
    else {
         p=powr(a,n/2);
         q=powr(a,n%2);
         k=(((p*p)%M)*q)%M;
         return k;
    }
}

int main()
{
	int t,x,i;
	ULL len=0;
	generate();
	si(t);
	while(t--){
		int n;
		si(n);
		for(i=0;i<9592;i++)pwr[i]=0;
		for(i=0;i<100001;i++)mul[i]=0;
		V[0]=1;
		for(i=1;i<=n;i++){
			si(Arr[i]);
			V[i]=0;
		}
	
	ULL num,ans=1;
		
		for(i=1;i<=n;i++){
				if(!V[i]){
					len=1;x=Arr[i];
					while(x!=i){
						V[x]=1;
						len++;
						x=Arr[x];
					}
				num=len;
				int cnt=0;
				if(primes[num]&&(!mul[num])){
					ans*=num;
					mul[num]=1;
					ans%=M;
				}
				else if(!primes[num]){
					for(int j=0;prm[j]<=sqrt(num);j++){
						cnt=0;
						while(num%prm[j]==0){
							cnt++;
							num/=prm[j];
						}
						if(cnt&&mul[prm[j]])cnt--;	
						
						if(cnt>pwr[j])pwr[j]=cnt;	
					}
				}
				}			
		}
		
		for(i=0;prm[i]<=sqrt(n);i++){
			if(pwr[i]){
				ans*=powr(prm[i],pwr[i]);
				ans=ans%M;	
			}	
		}
	
		printf("%llu\n",ans);	
	}
    
	return 0;
}
2

Your code fails for this case

7

3 7 6 1 5 2 4

ans -> 6

1 Like
3

Why do you require the header file bits stdc++.h="", I think it is not allowed to use personal header file. Correct me if I am wrong.

4

@ rahul_nexus It is a header file added to include all the headers required. You can refer to Useful C++ "library" - Codeforces for more insight.

1 Like
5

Thanks! it helped…:slight_smile: