Page **3** of **3**

Posted: **Fri Jul 16, 2004 4:13 pm**

by **Frostina**

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]

Posted: **Wed Mar 02, 2005 4:32 am**

by **Ryan Pai**

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

Posted: **Fri Aug 25, 2006 3:57 pm**

by **Kallol**

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.

Posted: **Wed Dec 05, 2007 8:35 pm**

by **Iffat**

what is the output of

Code: Select all

```
1 2147483647
11 2147483647
3 2147483645
```

thanx in advance

Posted: **Thu Dec 06, 2007 3:51 pm**

by **Iffat**

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

please help

Posted: **Thu Dec 06, 2007 4:31 pm**

by **sohel**

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?

Posted: **Thu Dec 06, 2007 4:35 pm**

by **Iffat**

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

thnx for helping

### Re: 10484 - Divisibility of Factors

Posted: **Thu Sep 13, 2012 8:57 pm**

by **Nafis0001**

**Thanks a lot brianfry713......I got accepted**

### Re: 10484 - Divisibility of Factors

Posted: **Fri Sep 14, 2012 10:24 pm**

by **brianfry713**

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.

### Re: 10484 - Divisibility of Factors

Posted: **Thu Sep 04, 2014 6:56 am**

by **matrix2220**

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