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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
