×

# [closed] Product of Divisior : Why i got WA??

 0 1 help me out from here please Problem link.. what is wrong with my solution??  #include 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[i]=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("\n"); else if(arr[N]==0) printf("0000\n"); else printf("%lld\n",arr[N]); } return 0; }  This question is marked "community wiki". asked 06 Jun '15, 11:19 1.1k●12●29 accept rate: 6%

### The question has been closed for the following reason "Duplicate Question" by rcsldav2017 18 Aug '15, 00:03

 1 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) ! answered 06 Jun '15, 15:33 125●8 accept rate: 20% @sumeet_varma again TLE... (06 Jun '15, 17:42) @sumeet_varma ...what should be ans for N==1?? (06 Jun '15, 18:12)

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,056
×591
×300
×145
×57
×17

question asked: 06 Jun '15, 11:19

question was seen: 1,414 times

last updated: 18 Aug '15, 00:03