EllysNumbers
SRM 534 · 2011-11-22 · by espr1t
SRM 534 · 2011-11-22 · by espr1t · Dynamic Programming, Simple Math
Problem Statement
Problem Statement
Elly's favourite number is n. She also has a list of distinct positive integers. We will call these integers special. She would like to know in how many ways she can represent n as a product of some pairwise relatively prime special integers.
You are given the
Notes
- When forming the product, the order of the special integers does not matter.
- There may be pairs of special integers that are not relatively prime. This just means that each valid product may contain at most one of those two special integers.
- You may assume that for each valid input the correct output fits into a long.
- Two positive integers are relatively prime if the only positive integer that divides both of them is 1. For example (5, 7) and (6, 35) are relatively prime, while (12, 18) and (7, 42) are not.
Constraints
- n will be between 2 and 10^18, inclusive.
- Each special integer will be between 1 and 10^9, inclusive.
- All special integers will be distinct.
- The number of special integers will be between 1 and 500, inclusive.
- special will contain between 1 and 50 elements, inclusive.
- Each element of special will contain between 1 and 50 characters, inclusive.
- Each character in each element of special will be either a digit or a space ('0'-'9', ' ').
- The concatenation of elements of special will represent a valid single-space separated list of integers (with no leading or trailing spaces). Each special integer will be written with no leading zeros.
Examples
0)
12
{"4 2 5 6 3"}
Returns: 1
There are two ways to represent 12 as a product of special integers: 3*4 and 2*6. Only the first way is valid because 2 and 6 are not relatively prime.
1)
42
{"1 2 3 4 5 6 7 13 14 21 42"}
Returns: 10
Forty-two can be represented as 2*3*7, 1*2*3*7, 2*21, 1*2*21, 3*14, 1*3*14, 6*7, 1*6*7, 42 and 1*42. All of those products contain only relatively prime special numbers, so the answer is 10.
2)
1337
{"1 13 42 666 2674"}
Returns: 0
Sometimes it is impossible to represent n as a product of special integers.
3)
1073741824
{"1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 1",
"6384 32768 65536 131072 262144 524288 1048576 2097",
"152 4194304 8388608 16777216 33554432 67108864 134",
"217728 268435456 536870912"}
Returns: 0
Although n can be represented in many ways, none of them is using only relatively prime special integers.
4)
7420738134810
{"435 625199055 4199 33263 17 222870 284870433 72093",
"2379 7 11 31 247110827 23 1771 81809 851968487 13 ",
"476379795 1001 5 435274114 38264554 7429 239906525",
" 3 227183706 887045414 606786670 3795 797605175 29",
" 30 747186719 19 2 562347843 74 2294 588002688 743",
"6429 703 591740547 36657492 37 444178205 1002001 2",
"17626404"}
Returns: 110
Don't forget to concatenate the elements of special.
80)
999999999999999989
{"999999937 999999929 999999893 999999883 999999797 ", "999999761 999999757 999999751 999999739 999999733 ", "999999677 999999667 999999613 999999607 999999599 ", "999999587 999999541 999999527 999999503 999999491 ", "999999487 999999433 999999391 999999353 999999337 ", "999999323 999999229 999999223 999999197 999999193 ", "999999191 999999181 999999163 999999151 999999137 ", "999999131 999999113 999999107 999999103 999999067 ", "999999059 999999043 999999029 999999017 999999001 ", "999998981 999998971 999998959 999998957 999998929 ", "999998921 999998917 999998903 999998869 999998863 ", "999998843 999998801 999998789 999998777 999998693 ", "999998689 999998687 999998683 999998663 999998653 ", "999998641 999998639 999998627 999998621 999998617 ", "999998609 999998563 999998537 999998533 999998509 ", "999998507 999998501 999998459 999998423 999998369 ", "999998339 999998309 999998269 999998261 999998243 ", "999998203 999998183 999998173 999998147 999998143 ", "999998141 999998137 999998119 999998107 999998081 ", "999998059 999998023 999998017 999998003 999997967 ", "999997891 999997871 999997811 999997793 999997787 ", "999997771 999997769 999997717 999997697 999997679 ", "999997673 999997643 999997639 999997627 999997589 ", "999997577 999997571 999997567 999997561 999997543 ", "999997489 999997457 999997403 999997357 999997331 ", "999997309 999997301 999997279 999997267 999997249 ", "999997241 999997237 999997181 999997133 999997099 ", "999997081 999997067 999997049 999997021 999996989 ", "999996983 999996919 999996913 999996901 999996827 ", "999996779 999996749 999996727 999996709 999996707 ", "999996689 999996677 999996671 999996649 999996643 ", "999996611 999996587 999996541 999996493 999996469 ", "999996407 999996383 999996359 999996341 999996329 ", "999996317 999996311 999996307 999996301 999996269 ", "999996259 999996247 999996227 999996223 999996199 ", "999996181 999996149 999996131 999996113 999996091 ", "999996073 999996071 999996043 999996037 999996031 ", "999996029 999996007 999995993 999995959 999995921 ", "999995911 999995903 999995819 999995813 999995809 ", "999995803 999995749 999995741 999995713 999995701 ", "999995681 999995677 999995663 999995651 999995629 ", "999995627 999995621 999995611 999995599 999995567 ", "999995561 999995531 999995431 999995419 999995413 ", "999995393 999995377 999995341 999995291 999995273 ", "999995261 999995257 999995239 999995141 999995111 ", "999995107 999995093 999994987 999994979 999994973 ", "999994951 999994913 999994903 999994883 999994867 ", "999994861 999994843 999994837 999994823 999994813 ", "999994781 999994771 999994763 999994753 999994747 ", "999994741 999994703 999994693 999994691 999994651"}
Returns: 0
Max test, all prime.
Submissions are judged against all 136 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EllysNumbers with a public method long long getSubsets(long long n, vector<string> special) · 136 test cases · 2 s / 256 MB per case