题目链接
HYSBZ2005
思路
根据题目意思，很明显跟gcd有关，因为路径上若有经过的点则点的个数为gcd(a,b)-1的个数
然后这题的答案就是求
按照套路来
设f(n)为gcd(a,b)=n的个数
则F(n)为gcd(a,b)=n及n的倍数的个数
答案就变为
然后我们只要能在下算出f(i)就可以解这道题
然后根据莫比乌斯倍数反演公式得出
我们枚举得到
到这里我们可以用分块除法加速，这样就能求出f(n)了
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+10;
int mu[maxn];
int prime[maxn],cnt;
bool vis[maxn];
int sum[maxn];
ll F[maxn];
void get_mu()
{
mu[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j])
{
mu[i*prime[j]]=-mu[i];
}
else
{
mu[i*prime[j]]=0;
break;
}
}
}
for(int i=1;i<maxn;i++)sum[i]=sum[i-1]+mu[i];
}
int main()
{
int n,m;
get_mu();
scanf("%d %d",&n,&m);
int minn=min(n,m);
ll ans = 0;
for(int i=1;i<=minn;i++)
{
int N = n/i;
int M = m/i;
ll temp = 0;
for(int j=1,last;i*j<=minn;j=last+1)
{
last=min(n/(n/j),m/(m/j));
temp+=1ll*(sum[last]-sum[j-1])*(N/j)*(M/j);
}
ans=ans+temp*(2*(i-1)+1);
}
cout<<ans<<endl;
}
|