题目链接
HDU4746
思路
这套题可以用前缀和的思想优化确实挺好，不过其实就是一个提取公因式的问题
首先根据套路莫比乌斯反演我们显然可以O(qnlogn)求出来，但是很明显会超时所以我们需要优化。
把答案的式子写出来之后我们可以枚举$\mu(i)$也就是枚举莫比乌斯函数值，然后通过分块优化，可以在O(nq)内求出答案
代码实现
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
#define ll long long
int mu[maxn];
int prime[maxn],cnt;
bool vis[maxn];
int sum[maxn];
int num[maxn];
ll F[maxn];
ll Sum[20][maxn];
vector<int>v;
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];
}
void init()
{
for(int i=2;i<maxn;i++)
{
int s=i;
int ccnt = 0;
for(int j=0;j<cnt&&prime[j]*prime[j]<=i;j++)
{
while(s%prime[j]==0)
{
ccnt++;
s/=prime[j];
}
}
if(s!=1)ccnt++;
num[i]=ccnt;
}
for(int i=1;i<maxn;i++)
{
for(int j=i;j<maxn;j+=i)
{
Sum[num[i]][j]+=mu[j/i];
}
}
for(int i=1;i<maxn;i++)
{
for(int j=0;j<20;j++)
{
Sum[j][i]+=Sum[j][i-1];
}
}
for(int i=0;i<maxn;i++)
{
for(int j=1;j<20;j++)
{
Sum[j][i]+=Sum[j-1][i];
}
}
}
int main()
{
int t;
scanf("%d",&t);
get_mu();
init();
while(t--)
{
int n,m,p;
scanf("%d %d %d",&n,&m,&p);
if(p>=20)
{
printf("%lld\n",1ll*n*m);
continue;
}
int minn = min(n,m);
ll ans = 0;
for(int i=1,last;i<=minn;i=last+1)
{
last=min(n/(n/i),m/(m/i));
ans+=1ll*(Sum[p][last]-Sum[p][i-1])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
}
|