You are not logged in. Please login at www.codechef.com to post your questions!

×

[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<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[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

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

closed 18 Aug '15, 00:03

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


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) !

link

answered 06 Jun '15, 15:33

sumeet_varma's gravatar image

7★sumeet_varma
1258
accept rate: 20%

@sumeet_varma again TLE...

(06 Jun '15, 17:42) rcsldav20175★

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

(06 Jun '15, 18:12) rcsldav20175★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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