Anup at Amrithapuri
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Anup recently visited Amrithapuri for ACM ICPC regional contest. A student walked up to Anup, gave him a paper which had a long programming question on it and asked him to solve it by 18th of January, 2015. As Anup was busy with school kids, he posted the question as cook off question, asking wider community to solve that question. Following is the question:
function f(A[0..N-1], L, R, P): if L > R: return f(A, R, L, P) ANSWER = 0 C = A[L..R] for each subset S of C: G = GCD(S) for each prime factor PF of G: if PF == P: ANSWER = MAX(ANSWER, SIZE(S)) return ANSWER
Line 5 loops over all 2^(R-L+1) subsets.
GCD(S) returns the Greatest common divisor of all the elements in S.
SIZE(S) returns the number of elements in S.
Given: N, M, A[0..N-1], B[0..M-1]
Where L = (B[i] + B[j]) % N
R = (B[i] - B[j] + N) % N
As the answer can be large. Output it modulo 1000000007.
First line has two integer N and M. Second line has N space separated integers representing the array A. Third line has M space separated integers representing the array B.
Output single integer which is the required answer modulo 1000000007
- 1 ≤ N ≤ 100000
- 1 ≤ M ≤ 500
- 1 ≤ A[i] ≤ 100000
- 0 ≤ B[i] < N
Input: 5 2 1 2 3 4 5 1 2 Output: 34
Here are the answers of few calls to function f()
f(A, 2, 0, 2) = 1
f(A, 2, 0, 5) = 0
f(A, 3, 4, 2) = 1
|Tags||anudeep2011, cook54, medium-hard, mo-algorithm|
|Time Limit:||7 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.