Product of Divisior : Why i got WA??

bug
divisors
perfetsquare
precomputation
sieve
wa

#1
  • help me out from here please

  • Problem link…

  • what is wrong with my solution??


    #include<bits/stdc++.h>
    using namespace std;
         **//driver program...**
       int main(){

                  	long long int T,N,i,j,K,arr[500001];

                    //precalculation...
    	        for(i=1 ;i <= 500000;i++)        arr*=1;

     	       for(i=2;i<=708;i++)
             		for(j=2*i;j<=500000;j+=i)
		              arr[j]=(arr[j]*i)%10000;

	       scanf("%lld",&T);

	       while(T--){

		       scanf("%lld",&N);
		       if(N==1) printf("

");
else if(arr[N]==0) printf("0000
“);
else printf(”%lld
",arr[N]);
}

          	    return 0;
       }

#2

I guess your ‘ct’ array stands for number of divisors and you are counting all divisors so that you can answer each query as (total divisors/2) ^ N which takes O(log(n)) time per query and O(n*log(n)) pre-processing. Instead of increasing ‘ct’ by 1 everywhere, you can instead multiply it by i. Obviously this means you initialize ct as 1 for all elements. Also now you don’t have to care about square root stuff. Each query can be answered simply as ct[n] which is O(1) !


#3

@sumeet_varma again TLE…


#4

@sumeet_varma …what should be ans for N==1??