http://acm.hdu.edu.cn/showproblem.php?pid=1695
1
/*
*
2
GCD(x,y)=k;在x小于b且y小于d时有多少组答案
3
2
4
1 3 1 5 1
5
1 11014 1 14409 9
6
7
Case 1: 9
8
Case 2: 736427
9
10
For the first sample input, all the 9 pairs of numbers are
11
(1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5).
12
*
*/
13
#include <iostream>
14
#include <cstdio>
15
#include <vector>
16
#include <cmath>
17
using
namespace
std;
18
const
int
Ni =
100010
;
19
int
phi[Ni];
20
vector<
int
>
prime[Ni];
21
long
long
sphi[Ni];
22
void
phi_table(
int
n)
23
{
24
phi[
1
]=
1
;
25
for
(
int
i=
2
;i<=n;i++)
if
(!
phi[i])
26
{
27
for
(
int
j=i;j<=n;j+=
i)
28
{
29
if
(!(phi[j])) phi[j]=
j;
30
prime[j].push_back(i);
31
phi[j]-=phi[j]/
i;
32
}
33
}
34
sphi[
0
]=
0
;
35
for
(
int
i=
1
;i<=n;i++
)
36
{
37
sphi[i]=sphi[i-
1
]+
phi[i];
38
}
39
}
40
int
dfs(
int
x,
int
b,
int
k)
///
求0到b中,与k不互质的个数，x为k的第x个质数因子
41
{
//
容斥定理
42
int
res=
0
;
43
for
(
int
i=x;i<prime[k].size();i++
)
44
res+=b/prime[k][i]-dfs(i+
1
,b/
prime[k][i],k);
45
return
res;
46
}
47
int
main()
48
{
49
int
t,i;
50
int
a,b,c,d,k,cs=
1
;
51
phi_table(
100005
);
52
scanf(
"
%d
"
,&
t);
53
for
(cs=
1
;cs<=t;cs++
)
54
{
55
scanf(
"
%d%d%d%d%d
"
,&a,&b,&c,&d,&
k);
56
if
(k==
0
) {printf(
"
Case %d: 0\n
"
,cs);
continue
;}
57
58
b/=k;d/=
k;
59
if
(b>
d) swap(b,d);
60
long
long
ans=
sphi[b];
61
for
(i=b+
1
;i<=d;i++
)
62
{
63
ans+=b-dfs(
0
,b,i);
64
}
65
printf(
"
Case %d: %I64d\n
"
,cs,ans);
66
}
67
return
0
;
68
}
