10484 - Divisibility of Factors
Moderator: Board moderators
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]
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 !
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.
what is the output of
thanx in advance
Code: Select all
1 2147483647
11 2147483647
3 2147483645
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.
-
- 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.
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!
-
- 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
---------------------------
AC Output
Hope That helps
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
Abdelrahman Ali (MaTrix)