p2195 Counting Zeroes (dhaka regionals)

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

p2195 Counting Zeroes (dhaka regionals)

Post by vinay » Tue Sep 26, 2006 4:21 am

http://acmicpc-live-archive.uva.es/nue ... hp?p=2195

as no one discusses about these problems at live archive board :oops:
I can't find how to solve this problem .........

Can anybody help me out........ :cry:


http://acmicpc-live-archive.uva.es/nue ... hp?p=2196

Also this problem........

Can anybody give me some recurence..... :oops:
If I will myself do hashing, then who will do coding !!!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Sep 26, 2006 9:00 am

This is not the place to discuss problems in the live archive!

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Tue Sep 26, 2006 10:54 am

but no one answers them on the live archive board........ :oops:
If I will myself do hashing, then who will do coding !!!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Tue Sep 26, 2006 1:18 pm

I think vinay is right, it seems no one reads the forums at the live archive so I don't think it's a bad idea to discuss them at the uva forum.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Tue Sep 26, 2006 2:03 pm

But i guess little joey wanted to say to post this in Algorithm not in v CXI :-)

Anyway:
2195 -> what does it means that last digit of n is 0 in base b? it means that n%b=0. and the next one? n%b^2=0?
2196 -> consinder set C={a1,a2,...,an}, look at the all subsets of C, and compare them with coefficients in our polynomial, then you should easily find out the formula

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

2195

Post by vinay » Tue Sep 26, 2006 5:35 pm

p 2195
true.....

but n can be 10^13, I can't go on checking for each digit :cry:

Or is it sufficient to find the prime factor n manipulate them to get the solution...... I m poor in combinatorics :oops:
If I will myself do hashing, then who will do coding !!!

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Tue Sep 26, 2006 6:12 pm

going upto sqrt of n tle.......
any other way ? :cry:
If I will myself do hashing, then who will do coding !!!

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Tue Sep 26, 2006 7:23 pm

first you can genarate up to sqrt(10^13) all primes, then you decomposite your input number. Using this decomposition you can generate all divisors of input number

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Tue Sep 26, 2006 9:36 pm

finding the divisors this way is time limiting :cry:

Please help.......... :oops:

do we need to generate all divisors here or some formula can be applied??????? :oops:
If I will myself do hashing, then who will do coding !!!

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Wed Sep 27, 2006 4:54 am

finding the prime factorization is itself time limiting :evil:
If I will myself do hashing, then who will do coding !!!

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Wed Sep 27, 2006 9:22 am

no, i got acc in 8s without special optimalization at LA

iz
New poster
Posts: 1
Joined: Wed Sep 27, 2006 8:59 am

explanation

Post by iz » Wed Sep 27, 2006 9:34 am

If you do the factorization properly it will not TL.
So first find all primes in the range [2, sqrt(n) ] using
http://en.wikipedia.org/wiki/Sieve_of_Eratosthene.
Now you have to find the number of the divisors of n, then count the divisors of the form x^2, x^3,..., x^k(where x divides n), and add them
to the total sum. Think for a while, how to count the divisors of the form
x, x^2, x^3....,x^3(where x divides n) when having n factorized.
If n = p1^q1*p2^q2*...*ps^qs, the number of the divisors is
(q1+1)*(q2+1)*...*(qs+1) ( I presume you now where this come from)

I will show you how to find divisors of the form x^2(where x divides n),
and for x^k just develop this idea further.
So x divides n => x=p1^r1*p2^r2*....ps^rs, for some ri in the range
[0,qi] => x^2 = p1^(r1*2)*p2^(r2*2)*...*ps^(rs*2). Now consider the
prime factor pi, it can participate in the products of this type in exactly
1+qi/2 different ways : pi^0, pi^2, pi^4..... pi^(i/2), now using the same
logic as in counting the number of different divisors you will find that the
number is (1+q1/2)*(1+q2/2)*(1+q3/2)*...*(1+qs/2)

*sorry if my English contains errors ;)

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Fri Sep 29, 2006 2:55 am

could u explain the process for 20 (twenty)...
thanks..
If I will myself do hashing, then who will do coding !!!

Rainy Day
New poster
Posts: 8
Joined: Sun Sep 10, 2006 9:03 am

Post by Rainy Day » Fri Sep 29, 2006 4:06 am

divisors formula something like this :
( q1+1)(q2+1).........(qn+1) -2 ; u must extracted first and last divisor.
20=2x2x5
so , there r (2+1)(1+1) -2 = 4 divisors.
there r (1 + 2/2)(1 + 1 / 2) = 2 divisor of the form x^2,x^3,...........................
so ,total = 4+2 = 6

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Sep 29, 2006 6:39 am

I don't think that is correct (the case for 20) - you get the correct answer, but you don't remove first and last - you just remove 1 as a divisor every time you count them (because 1=1^2=1^3...).

Try 8 = 2^3, your algorithm gives 6 instead of 5 (1000 in base 2, 20 in base 4, 10 in base 8).

Post Reply

Return to “ACM ICPC Archive Board”