## 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
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= { 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, df, 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
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.
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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
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
i can't understand why 0 -5 and 0 5 s outputs are different?
please help
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
but i got that from Ryan Pai's output....

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

### Re: 10484 - Divisibility of Factors

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

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

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)