p2195 Counting Zeroes (dhaka regionals)
Moderator: Board moderators
p2195 Counting Zeroes (dhaka regionals)
http://acmicpclivearchive.uva.es/nue ... hp?p=2195
as no one discusses about these problems at live archive board
I can't find how to solve this problem .........
Can anybody help me out........
http://acmicpclivearchive.uva.es/nue ... hp?p=2196
Also this problem........
Can anybody give me some recurence.....
as no one discusses about these problems at live archive board
I can't find how to solve this problem .........
Can anybody help me out........
http://acmicpclivearchive.uva.es/nue ... hp?p=2196
Also this problem........
Can anybody give me some recurence.....
If I will myself do hashing, then who will do coding !!!

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 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
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
2195
p 2195
true.....
but n can be 10^13, I can't go on checking for each digit
Or is it sufficient to find the prime factor n manipulate them to get the solution...... I m poor in combinatorics
true.....
but n can be 10^13, I can't go on checking for each digit
Or is it sufficient to find the prime factor n manipulate them to get the solution...... I m poor in combinatorics
If I will myself do hashing, then who will do coding !!!
explanation
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
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