1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <stdio.h>
#include <stdlib.h>
#define ul unsigned long
#define LEN 1000001
#define P_LEN 78498
ul PRIMES[P_LEN];
ul *psearch(ul key)
{
ul lo = 0, hi = P_LEN, mid;
while (lo < hi) {
if (key < PRIMES[mid = (lo + hi) / 2])
hi = mid;
else
lo = mid + 1;
}
return PRIMES + lo;
}
void factorange(ul *d, ul prime, ul start, ul stop)
{
ul i = 0;
for (; stop; i += stop /= prime);
for (start -= 1; start; i -= start /= prime);
*d *= i * 2 + 1;
*d %= 111539786;
}
int main()
{
FILE *fi = fopen("LCM.INP", "r"), *fo = fopen("LCM.OUT", "w");
char t;
ul a, b, c = 0, d, *i = calloc(LEN, sizeof(ul)), *j;
for (a = 2; a < 1001; a++)
if (!i[a]) {
for (b = a * a; b < LEN; b += a)
i[b] = 1;
PRIMES[c++] = a;
}
for (; a < LEN; a++)
if (!i[a])
PRIMES[c++] = a;
free(i);
fscanf(fi, "%hhd\n", &t);
for (; t--;) {
fscanf(fi, "%ld %ld\n", &a, &b);
j = psearch(b);
for (d = 1, i = PRIMES; i < j; factorange(&d, *i++, a, b));
fprintf(fo, "%ld\n", d);
}
fclose(fi);
fclose(fo);
return 0;
}
|
