1387: #6028. 「from CommonAnts」质数计数 II

Memory Limit:512 MB Time Limit:3.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

求满足 1<p≤n1<p \leq n1<pn 的质数中,模 mmm 等于 0,1,2,...,m−10,1,2,...,m-10,1,2,...,m1 的分别有多少个。

输入格式

一行两个整数 n,mn,mn,m

输出格式

输出共 mmm 行,每行一个整数,第 iii 行表示 1<p≤n1<p \leq n1<pn 的质数中模 mmm 等于 i−1i-1i1 的质数个数。

样例

样例输入 1

7 3

样例输出 1

1
1
2

样例解释 1

333 等于 000 的:{3}\{3\}{3}
333 等于 111 的:{7}\{7\}{7}
333 等于 222 的:{2,5}\{2,5\}{2,5}

样例输入 2

100000 6

样例输出 2

0
4784
1
1
0
4806

数据范围与提示

对于 25%25\%25% 的数据,1≤n≤1041\leq n\leq 10^41n104
对于 50%50\%50% 的数据,1≤n≤1071\leq n\leq 10^71n107
对于 75%75\%75% 的数据,1≤n≤1091\leq n\leq 10^91n109
对于 100%100\%100% 的数据,1≤n≤3×1010,1<m≤12,n>m1\leq n\leq 3\times 10^{10},1<m \leq 12,n>m1n3×1010,1<m12,n>m