Anup at Amrithapuri

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Problem description
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..N1], 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
Clarifications:
Line 5 loops over all 2^(RL+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..N1], B[0..M1]
Required:
Where L = (B[i] + B[j]) % N
R = (B[i]  B[j] + N) % N
As the answer can be large. Output it modulo 1000000007.
Input
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
Output single integer which is the required answer modulo 1000000007
Constraints
 1 ≤ N ≤ 100000
 1 ≤ M ≤ 500
 1 ≤ A[i] ≤ 100000
 0 ≤ B[i] < N
Example
Input: 5 2 1 2 3 4 5 1 2 Output: 34
Explanation
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
Author:  anudeep2011 
Tester:  xiaodao 
Editorial  http://discuss.codechef.com/problems/ANUAAA 
Tags  anudeep2011, cook54, mediumhard, moalgorithm 
Date Added:  6012015 
Time Limit:  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions