双倍经验就是爽.jpg
思路
和YY的GCD类似但是更加简单了
类似的推一波公式即可
$$
F(n)=sum_{n|d}f(d)
$$
$$
f(n)=sum_{n|d}mu(frac{d}{n})F(d)
$$
$$
F(d)=lfloorfrac{n}{d}rfloortimeslfloorfrac{m}{d}rfloor
$$
$$
f(x)=sum_{x|d}mu(frac{d}{x})timeslfloorfrac{n}{d}rfloortimeslfloorfrac{m}{d}rfloor
$$
$$
f(x)=sum_{t=1}^{lfloorfrac{n}{x}rfloor}mu(t)timeslfloorfrac{n}{xtimes t}rfloortimeslfloorfrac{m}{xtimes t}rfloor
$$
然后整除分块即可
代码
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
|
#include <algorithm>
#include <cstring>
using namespace std;
int T,n,m,mu[51000],iprime[51000],isprime[51000],summu[51000],cnt,k;
void (int n){
isprime[1]=true;
mu[1]=1;
for(int i=2;i<=n;i++){
if(!isprime[i])
iprime[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&iprime[j]*i<=n;j++){
isprime[iprime[j]*i]=true;
mu[iprime[j]*i]=-mu[i];
if(i%iprime[j]==0){
mu[iprime[j]*i]=0;
break;
}
}
}
for(int i=1;i<=n;i++)
summu[i]=summu[i-1]+mu[i];
}
long long f(int k){
long long ans=0;
for(int l=1,r;l<=min(n,m);l=r+1){
r=min((n/(n/(l))),(m/(m/(l))));
ans+=1LL*(summu[r]-summu[l-1])*(n/(l*k))*(m/(l*k));
}
return ans;
}
int main(){
prime(50100);
scanf("%d",&T);
while(T--){
scanf("%d %d %d",&n,&m,&k);
if(n<m)
swap(n,m);
printf("%lldn",f(k));
}
return 0;
}
|
近期评论