Link to the pdf version on UVa OJ
Given two integers N and D, you will have to find how many of the factors of N! are divisible by D.
The above sentence is the description of the problem. Let's start with an example. Let N be 5 and D be 10.
If any factors of N! must be divisible by D, first N! must be divisible by D itself. Let's factorize N! and D.
5! = 2^3 * 3^1 * 5^1
10 = 2^1 * 5^1
so 5! / 10 would be 2^2 * 3^1. This means we took a "10" out of 5! and 2^2 * 3^1 remains. Now we have options to take zero, one or two 2's and zero or one 3's. So there are 3 options for 2 and 2 options for 3. The answer would be 6. There are 6 different factors of 5! that are divisible by 10.
If you code in C++ or Java, be careful, the result could get large, you should use long long in C++, and long in Java.
Implementation:
It's not hard to factorize N!, because N is <= 100. After factorizing N! iterate over factors and for each pair (prime, power) in the factors try to divide D by prime as many times as possible, and by each division decrease power by one. After the iteration ends D must be 1 or -1, otherwise N! is not divisible by D in the first place.
If D is 1 or -1, then you should iterate once more over the factors of N! that you just modified (decreased powers as many time as possible) and calculate the result using the multiplication principle.
If D is -1 you should multiply the result by 2 in the end. why?
The above sentence is the description of the problem. Let's start with an example. Let N be 5 and D be 10.
If any factors of N! must be divisible by D, first N! must be divisible by D itself. Let's factorize N! and D.
5! = 2^3 * 3^1 * 5^1
10 = 2^1 * 5^1
so 5! / 10 would be 2^2 * 3^1. This means we took a "10" out of 5! and 2^2 * 3^1 remains. Now we have options to take zero, one or two 2's and zero or one 3's. So there are 3 options for 2 and 2 options for 3. The answer would be 6. There are 6 different factors of 5! that are divisible by 10.
 | |
| N=5, D=10 |
If you code in C++ or Java, be careful, the result could get large, you should use long long in C++, and long in Java.
Implementation:
It's not hard to factorize N!, because N is <= 100. After factorizing N! iterate over factors and for each pair (prime, power) in the factors try to divide D by prime as many times as possible, and by each division decrease power by one. After the iteration ends D must be 1 or -1, otherwise N! is not divisible by D in the first place.
If D is 1 or -1, then you should iterate once more over the factors of N! that you just modified (decreased powers as many time as possible) and calculate the result using the multiplication principle.
If D is -1 you should multiply the result by 2 in the end. why?
No comments:
Post a Comment