10484 - Divisibility of Factors

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

Post by Frostina » Fri Jul 16, 2004 4:13 pm

I consider long long & if d<0 but still got wa,
could anyone plz help me?

[c]#include <iostream>
using namespace std;

int main(void) {
int primes[25]= { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,
47,53,59,61,67,71,73,79,83,89,97 };
int pnums[25], df[25], n, i, j, fact, out;
long long d;
while (cin>>n>>d) {
if (!n&&!d) break;
if (d<0) d = -d;
for (i=0;i<25;i++)
pnums = df = 0;
for (i=0;i<25&&d!=1;i++) {
while (!(d%primes)) {
d /= primes;
df++;
}
}
/* if d has prime factors which are bigger than 100 */
if (d>1) {
cout << "0" << endl;
continue;
}
for (i=2;i<=n;i++) {
fact = i;
for (j=0;j<25&&fact!=1;j++)
while (!(fact%primes[j])) {
fact /= primes[j];
pnums[j]++;
}
}
for (i=0;i<25;i++) {
pnums -= df;
if (pnums<0) break;
}
if (i<25) { cout << "0" << endl; continue; }
for (i=0,out=1;i<25;i++)
out *= (pnums+1);
cout << out << endl;
}
return 0;
} [/c]
Thanks for your help ! ;)

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Wed Mar 02, 2005 4:32 am

Here's the correct output jamu. It appears you're off by one on cases where |d|=1
1
0
0
0
1
1
0
0
0
1
1
0
0
0
0
1
2
0
2
1
0
0
0
0
1
0
0
2
2
4
0
4
2
2
0
0
1
0
0
480
880
0
242880
94133433139200
117666791424000
116177338368000
38603278909440000
38205306961920000
35101125771264000
39001250856960000
39001250856960000
I'm always willing to help, if you do the same.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Fri Aug 25, 2006 3:57 pm

Another problem in Jamu's inputs.
The problem statement said 0<|D| .... so D can not be equal to 0. But in Jamu's input there were D=0 number of times.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Post by Iffat » Wed Dec 05, 2007 8:35 pm

what is the output of

Code: Select all

       1 2147483647
       11 2147483647
       3 2147483645
thanx in advance :)

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Post by Iffat » Thu Dec 06, 2007 3:51 pm

i can't understand why 0 -5 and 0 5 s outputs are different?
please help

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Dec 06, 2007 4:31 pm

Iffat wrote:i can't understand why 0 -5 and 0 5 s outputs are different?
please help
What do you mean?
The output of both of them is 0!! How are they different?

Iffat
New poster
Posts: 25
Joined: Sat Jul 22, 2006 9:47 am

Post by Iffat » Thu Dec 06, 2007 4:35 pm

but i got that from Ryan Pai's output....

thnx for helping :o

Nafis0001
New poster
Posts: 6
Joined: Fri Mar 23, 2012 10:02 pm

Re: 10484 - Divisibility of Factors

Post by Nafis0001 » Thu Sep 13, 2012 8:57 pm

Thanks a lot brianfry713......I got accepted
Last edited by Nafis0001 on Sat Sep 15, 2012 5:02 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10484 - Divisibility of Factors

Post by brianfry713 » Fri Sep 14, 2012 10:24 pm

Try rewriting your code to not use any doubles. Be careful to avoid overflow.

I tested the judge's input and 0<=N<=100 and 0<D<=2^31-1
D is always positive.
Check input and AC output for thousands of problems on uDebug!

matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

Re: 10484 - Divisibility of Factors

Post by matrix2220 » Thu Sep 04, 2014 6:56 am

Given N and D, you are required to count number of N! factors that are Divisible by D.

The trivial solution is to find N!, then find it's prime factors and find prime factors of D then
subtract the common powers and multiply all powers.
ex. N = 10 , D = 2
10! = 3628800 = 2^8 3^4 5^2 7^1
2 = 2^1
We now want to form a number from the prime factor set of N! that is divisible by D and is a factor of N!,
so it must contain D as a factor.
prime factors of N! can be raised to power from 0 to it's current power. ex. 2^8 , 2^7 , ... , 2^0
So we can form factors of N! from this combination of powers.
We have a total of 9 * 5 * 3 * 2 = 270 factors for 10!
Now we want to count the factors that are divisible by D, so we need to ensure that we leave the required
power of prime factors of D and count the remaining combinations
We will have 8 5 3 2 = 240 factors of N! that are divisible by D

The Only Problem with this solution is finding N!. When N = 100, How are you supposed to find 100! ?
The solution for that is to use Prime Factorial Factorization by which you can represent 100! as the product
of it's prime factors. Another problem is the Big value of D, you should use an efficient prime factorization
to factorize D into it's prime factors.

You should notice that, there is 2 conditions such that there will be a solution:
1) All factors of D must exist in N
2) Powers Of D's factors is <= powers of corresponding N's Factors

----------
Resources:
----------
- Prime Factorization:
http://www.vogella.com/tutorials/JavaAl ... ticle.html

- Prime Factorization of factorial:
http://mathforum.org/library/drmath/view/67291.html
https://answers.yahoo.com/question/inde ... 709AAVJlxi
http://blmath.wordpress.com/2009/04/27/ ... actorials/

- Legendre's Theorem
http://www.cut-the-knot.org/blue/LegendresTheorem.shtml
----------------
Test Cases:
----------------
Input

Code: Select all

10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
2 1
2 3
2 5
5 7
5 9
3 2
4 1
2 8
10 12
2 16
2 10
0 0
---------------------------
AC Output

Code: Select all

270
240
216
210
180
192
135
180
162
160
2
0
0
0
0
2
8
0
168
0
0
Hope That helps :)
Abdelrahman Ali (MaTrix)

Post Reply

Return to “Volume 104 (10400-10499)”