10484 - Divisibility of Factors

[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]

[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

[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.

[Iffat]

what is the output of

Code: Select all

       1 2147483647
       11 2147483647
       3 2147483645

thanx in advance

[Iffat]

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

[sohel]

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]

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

thnx for helping

[Nafis0001]

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

[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.

[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