Algorithms examples
1. Arrays of Fibonacci
A series of natural numbers of length N smaller than M. is given.
Find the maximum length of the Fibonacci array filament so that it can be formed from the given numbers and print the indexes of the elements of the given set that form this Fibonacci sub-array.
Find the maximum length of the Fibonacci array filament so that it can be formed from the given numbers and print the indexes of the elements of the given set that form this Fibonacci sub-array.
Input
In the first line of the standard input there are natural numbers N and M, which represent the number of elements and the maximum possible value of the elements of the given set.
In the second row, there are N natural numbers that represent the set array.
Output
On the standard output in the first row, print the number of elements of the longest Fibonacci sub-array that can be formed and print indexes of the elements of a given set that form this Fibonacci sub-array. If there are two numbers with a different index in a row, take a smaller index. Indices are written in such a way that the elements of the array that they index can form the Fibonacci sub-array.
Limitations
M <= 10,000;
N <= 10 000 000;
Example
Input
12
20
Output
2 4 6 8 10 11 13 4 3 2 1 1
4
10 11 0
In the first line of the standard input there are natural numbers N and M, which represent the number of elements and the maximum possible value of the elements of the given set.
In the second row, there are N natural numbers that represent the set array.
Output
On the standard output in the first row, print the number of elements of the longest Fibonacci sub-array that can be formed and print indexes of the elements of a given set that form this Fibonacci sub-array. If there are two numbers with a different index in a row, take a smaller index. Indices are written in such a way that the elements of the array that they index can form the Fibonacci sub-array.
Limitations
M <= 10,000;
N <= 10 000 000;
Example
Input
12
20
Output
2 4 6 8 10 11 13 4 3 2 1 1
4
10 11 0
2. Factoring
N is numbered. It is necessary to factorize each number, i.e. write it as a product of free factors. Each number is factorized in the format p1 ^ a1 * p2 ^ a2 * ... * pk ^ ak, where p1 ≤ p2 ≤ ... ≤ pk are all the simple factors of the given number (in the growing order), and a1, a2, .. ., ak - their respective exhibitors. There must be no space between the numbers and symbols '*' and '^'. Also, if the exhibitor of a number is equal to 1, it should be printed out anyway.
Input
In the first line of the standard input there is a natural number of n. In the next n rows there is one full number that should be factorized.
Output
On the standard output for each number, print in a special order its factoring in the format described above, in the order given at the input.
Limitations
1 ≤ n ≤ 200,000,
2 ≤ bi ≤ 200,000.
In the first line of the standard input there is a natural number of n. In the next n rows there is one full number that should be factorized.
Output
On the standard output for each number, print in a special order its factoring in the format described above, in the order given at the input.
Limitations
1 ≤ n ≤ 200,000,
2 ≤ bi ≤ 200,000.
3. Pairs of prime numbers
Given is a natural number N. Determine how many pairs of prime numbers p and q are so that p ≤ q and that p + q is also a free number that is less than or equal to N.
Input
In the first and only row of the standard input there is a natural number N.
Output
In the first and only row of the standard output, the required number of pairs of prime numbers is written.
Limitations
1 ≤ N ≤ 1,000,000
In the first and only row of the standard input there is a natural number N.
Output
In the first and only row of the standard output, the required number of pairs of prime numbers is written.
Limitations
1 ≤ N ≤ 1,000,000
Example
Input
6
Output
1
Explanation of the case
There is only one pair that meets the conditions and that is (2, 3). Indeed, 2 and 3 are free numbers and 2 + 3 is a free number that is less than or equal to 6.
Input
6
Output
1
Explanation of the case
There is only one pair that meets the conditions and that is (2, 3). Indeed, 2 and 3 are free numbers and 2 + 3 is a free number that is less than or equal to 6.
4. Faktoring 2
For the numbers p and q we say that they are k-simple if they are free and there are exact numbers between them. You are given the numbers N and k. It is known that the number N is either free or can be written in the form of a product p1 · p2 · p3 · · · · pm, where for each 1 ≤ and ≤ m -1, pi <p_ {i + 1} and pi and p_ {i + 1} are k-free distances. Unfortunately, we do not know the number m or the numbers pi - it is your task to factor N, that is, to write it in the form of product numbers.
Input
In one test case, several N numbers should be factorized.
In the first line of the standard input there is a natural number T - number of pairs (N, k) from the description of the problem. In each of the following T rows, there are, in turn, the numbers N and k, separated by a space.
Output
On the standard output it is necessary to print T rows, where in the second order it is necessary to print the factorization of the i-th number N from the input. Make N numbers in a rising order and print the '*' (asterisk) without spaces and quotation marks between each of the two factors (see example).
Limitations
1 ≤ T ≤ 5,000
2 ≤ N ≤ 1.000.000.000.000
0 ≤ k ≤ 100
In one test case, several N numbers should be factorized.
In the first line of the standard input there is a natural number T - number of pairs (N, k) from the description of the problem. In each of the following T rows, there are, in turn, the numbers N and k, separated by a space.
Output
On the standard output it is necessary to print T rows, where in the second order it is necessary to print the factorization of the i-th number N from the input. Make N numbers in a rising order and print the '*' (asterisk) without spaces and quotation marks between each of the two factors (see example).
Limitations
1 ≤ T ≤ 5,000
2 ≤ N ≤ 1.000.000.000.000
0 ≤ k ≤ 100
Example
Input
4
238 2
11 0
2431 0
10 1
Output
2 * 7 * 17
11
11 * 13 * 17
2 * 5
Explanation of the case
For example. in the first pair (N = 238, k = 2), the numbers 2 and 7 are k-free since they are free and there are exactly two free numbers between them: 3 and 5. Similarly for the numbers 7 and 17. Factoring of the number N under the stated conditions is, of course, unique.
Input
4
238 2
11 0
2431 0
10 1
Output
2 * 7 * 17
11
11 * 13 * 17
2 * 5
Explanation of the case
For example. in the first pair (N = 238, k = 2), the numbers 2 and 7 are k-free since they are free and there are exactly two free numbers between them: 3 and 5. Similarly for the numbers 7 and 17. Factoring of the number N under the stated conditions is, of course, unique.
5. GCD and LCM
Determine the greatest common divisor (GCD) and Least common multiple(LCM) in an efficient way using the EUCLID algorithm
6. The greatest GCD
A series of natural numbers is given, and from n elements. In one move, you can select arbitrary two adjacent numbers in a row and replace them with their summation. For example, if we have chosen the numbers ai and ai + 1, the sequence (a1, a2, ..., ai, ai + 1, ... an) becomes (a1, a2, ..., ai + ai + ... an). We can then repeat this on newly created sequences (note that the number of elements of the string is reduced by 1 each time).
Apply a certain number of moves over the starting sequence so that in the end we get exactly the numbers whose largest common divider is greatest possible.
Apply a certain number of moves over the starting sequence so that in the end we get exactly the numbers whose largest common divider is greatest possible.
7. GCD two products
Given n are natural numbers A1, A2, ..., An and m of natural numbers B1, B2, ..., Bm. It was calculated to calculate GCD (A1 · A2 ··· An, B1 · B2 ··· Bm). However, as this number can be very large, calculate only its remainder for a share of 1,000,000,000.
Input
In the first line of the standard input there is a natural number n. The second line contains n natural numbers - A1, A2, ..., An, separated by a space. In the third row there is a natural number m. The fourth row contains m natural numbers - B1, B2, ..., Bm, separated by a space.
Output
In the first and only row of the standard output, the rest of the share of the requested NZD with a number of 1,000,000,000 is to be written.
Limitations
1 ≤ n, m ≤ 1,000
1 ≤ Ai, Bi <1.000 million
Example
Input
3
358572 83391967 82
3
50229961 1091444 8863
Output
12028
Explanation of the case
Valid GCD (358572 · 83391967 · 82, 50229961 · 1091444 · 8863) = NZGCDD (2451966000072168, 485897929014301292) = 408661000012028. How is 408661000012028 MOD 1.000.000.000 = 12028, this number is a solution.
In the first line of the standard input there is a natural number n. The second line contains n natural numbers - A1, A2, ..., An, separated by a space. In the third row there is a natural number m. The fourth row contains m natural numbers - B1, B2, ..., Bm, separated by a space.
Output
In the first and only row of the standard output, the rest of the share of the requested NZD with a number of 1,000,000,000 is to be written.
Limitations
1 ≤ n, m ≤ 1,000
1 ≤ Ai, Bi <1.000 million
Example
Input
3
358572 83391967 82
3
50229961 1091444 8863
Output
12028
Explanation of the case
Valid GCD (358572 · 83391967 · 82, 50229961 · 1091444 · 8863) = NZGCDD (2451966000072168, 485897929014301292) = 408661000012028. How is 408661000012028 MOD 1.000.000.000 = 12028, this number is a solution.