A6811. 「SNOI2017」遗失的答案
编程题
NOI/NOI+/CTSC
知识点
题目描述
小皮球在计算出答案之后，买了一堆皮肤，他心里很开心，但是一不小心，就忘记自己买了哪些皮肤了。= =|||
万幸的是，他还记得他把所有皮肤按照 $1\sim N$ 来编号，他买来的那些皮肤的编号（他至少买了一款皮肤），最大公约数是 $G$，最小公倍数是 $L$。
现在，有 $Q$ 组询问，每组询问输入一个数字 $X$，请你告诉小皮球，有多少种合法的购买方案中，购买了皮肤 $X$？
因为答案太大了，所以你只需要输出答案 $\bmod 1000000007$ 即可。
万幸的是，他还记得他把所有皮肤按照 $1\sim N$ 来编号，他买来的那些皮肤的编号（他至少买了一款皮肤），最大公约数是 $G$，最小公倍数是 $L$。
现在，有 $Q$ 组询问，每组询问输入一个数字 $X$，请你告诉小皮球，有多少种合法的购买方案中，购买了皮肤 $X$？
因为答案太大了，所以你只需要输出答案 $\bmod 1000000007$ 即可。
输入格式
第一行，三个数字 $N,G,L$，如题意所示。
第二行，一个数字 $Q$，表示询问个数。
第三行，$Q$ 个数字，表示每个询问所问的 $X$。
第二行，一个数字 $Q$，表示询问个数。
第三行，$Q$ 个数字，表示每个询问所问的 $X$。
输出格式
对于每一组询问，在一行中单独输出一个整数，表示这个询问的答案。
输入输出样例
输入 #1
5 1 30 5 1 2 3 4 5
输出 #1
1 2 2 0 2
说明/提示
$30\%$ 的数据：$N\leq 20$
$50\%$ 的数据：$N\leq 1000$
$70\%$ 的数据：$N\leq 100000$
$100\%$ 的数据：$N,G,L\leq 10^8,Q\leq 10^5,1\leq X\leq 10^8$
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000 ms。
$50\%$ 的数据：$N\leq 1000$
$70\%$ 的数据：$N\leq 100000$
$100\%$ 的数据：$N,G,L\leq 10^8,Q\leq 10^5,1\leq X\leq 10^8$
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000 ms。