2 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define int long long #define N 10000000 int pr,p[N+10],mu[N+10]; bool v[N+10]; int sum[N+10]; void init(){ memset(v,0,sizeof(v)); pr=0;mu[0]=0;mu[1]=1; // 时间复杂度O(n) for(int i=2;i<=N;i++){ if(!v[i])p[++pr]=i,mu[i]=-1,v[i]=1,sum[i]=1; for(int j=1;j<=pr&&i*p[j]<=N;j++){ v[i*p[j]]=1; if(i%p[j]==0){ sum[i*p[j]]=mu[i]; mu[i*p[j]]=0; break; } sum[i*p[j]]=-sum[i]+mu[i]; mu[i*p[j]]=-mu[i]; } sum[i]+=sum[i-1]; } /* 下面方法计算sum会TLE 时间复杂度O(nlogn) for(int i=1;i<=pr;i++){ for(int j=1;j*p[i]<=N;j++){ sum[j*p[i]]+=mu[j]; } } for(int i=1;i<=N;i++)sum[i]+=sum[i-1];*/ } int calc(int n,int m){ if(n>m)swap(n,m); int ans=0; for(int l=1,r;l<=n;l=r+1){ r=min(n/(n/l),m/(m/l)); ans+=(sum[r]-sum[l-1])*(n/l)*(m/l); } return ans; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); init(); int t;cin>>t; while(t--){ int n,m;cin>>n>>m; cout<<calc(n,m)<<'\n'; } return 0; } -
0
问题
给出 ，求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lbrack\gcd(i,j) \in prime\rbrack$。
题解
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lbrack\gcd(i,j) \in prime\rbrack$ $=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=1}^n \lbrack \gcd(i,j)=k \rbrack \lbrack k \in prime\rbrack$ 经典转换 $=\sum\limits_{k=1}^n\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}} \lbrack \gcd(i,j)=1 \rbrack \lbrack k \in prime\rbrack$ $=\sum\limits_{k=1}^n\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}}\sum\limits_{d|\gcd(i,j)}\mu(d) \lbrack k \in prime\rbrack$ $=\sum\limits_{k=1}^n\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}}\sum\limits_{d=1}^{\frac{n}{k}} \lbrack d|i \rbrack \lbrack d|j \rbrack \mu(d) \lbrack k \in prime\rbrack$ $=\sum\limits_{k=1}^n\sum\limits_{d=1}^{\frac{n}{k}} \mu(d)\sum\limits_{i=1}^{\frac{n}{k}}\lbrack d|i \rbrack \sum\limits_{j=1}^{\frac{m}{k}}\lbrack d|j \rbrack \lbrack k \in prime\rbrack$ $=\sum\limits_{k=1}^n\sum\limits_{d=1}^{\frac{n}{k}} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \lbrack k \in prime \rbrack$ $=\sum\limits_{k \in prime}\sum\limits_{d=1}^{\frac{n}{k}} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$ 此时，只要最外层质数
枚举 ，即可解决。
但会50分超时，
毕竟需要两层循环。超时50分代码如下：
#include<bits/stdc++.h> #define LL long long using namespace std; const int N=1e7; int pr, p[N+10];LL mu[N+10]; bool v[N+10]; void init() { memset(v,0,sizeof(v)); pr=0;mu[0]=0;mu[1]=1; for(int i=2;i<=N;i++) { if(!v[i]) p[++pr]=i, mu[i]=-1; for(int j=1;j<=pr&&p[j]*i<=N;j++) { v[i*p[j]]=true; if(i%p[j]==0) {mu[i*p[j]]=0; break;} mu[i*p[j]]=-mu[i]; } } for(int i=1;i<=N;i++)mu[i]+=mu[i-1]; } LL calc(int n, int m) { LL ans=0; for(int i=1;i<=pr && p[i]<=n;i++) { int tn=n/p[i],tm=m/p[i]; for(int l=1,r;l<=tn;l=r+1) { r=min(tn/(tn/l), tm/(tm/l)); ans+=(mu[r]-mu[l-1])*(tn/l)*(tm/l); } } return ans; } int main() { init(); int T;scanf("%d",&T); while(T--) { int n,m;scanf("%d%d", &n, &m);if(n>m)swap(n,m); printf("%lld\n", calc(n, m)); } return 0; }继续改进 $=\sum\limits_{k \in prime}\sum\limits_{d=1}^{\frac{n}{k}} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$ 观察： 好办， 确定了直接前缀和。
但 $\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$ 需要枚举 。设 ，代入 $=\sum\limits_{k \in prime}\sum\limits_{\frac{T}{k}=1}^{\frac{n}{k}} \mu(\frac{T}{k}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$ 默认： 当 是 的倍数才有效。
即： 等价于 $\mu(\frac{T}{k})\lbrack k$=\sum\limits_{k \in prime}\sum\limits_{T=1}^n \mu(\frac{T}{k}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$ $\sum\limits_{\frac{T}{k}=1}^{\frac{n}{k}} \mu(\frac{T}{k})$ 和 是等价转换。 $=\sum\limits_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum\limits_{k \in prime}\mu(\frac{T}{k})$ 经典操作： 可以前缀和，这点对于初学者不容易看出，也是因这些不容易看出和处理的前缀和，为这类题提供了思维难度和考察区别度。 设
即枚举 的所有质因子（注：不是枚举 约数） , 累加 ，这个累加的过程需要灵活处理：枚举每个质数 ，再枚举 的倍数 ，初始化代码如下：
F[0]=0;
for(int i=1;i<=pr;i++)
for(int j=p[i];j<=N;j+=p[i])
F[j]+=mu[j/p[i]];
for(int i=1;i<=N;i++)F[i]+=F[i-1];$=\sum\limits_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor F(T)$ 两层for有时也能过，但是往往高质量的题要求只有一层for才能ac 具体代码如下：
#include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e7; int pr, p[N + 10]; LL mu[N + 10], F[N + 10]; bool v[N + 10]; void init() { memset(v,0,sizeof(v)); pr=0;mu[0]=0;mu[1]=1; for(int i=2;i<=N;i++) { if(!v[i])p[++pr]=i,mu[i]=-1; for(int j=1;j<=pr && p[j]*i<=N;j++) { v[i*p[j]]=true; if(i%p[j]==0){mu[i*p[j]]=0;break;} mu[i*p[j]]=-mu[i]; } } F[0]=0; for(int i=1;i<=pr;i++) for(int j=p[i];j<=N;j+=p[i]) F[j]+=mu[j/p[i]]; for(int i=1;i<=N;i++)F[i]+=F[i-1]; } LL calc(int n, int m) { if(n>m)swap(n,m); LL ans=0; for(int l=1,r;l<=n;l=r+1) { r=min(n/(n/l),m/(m/l)); ans+=(F[r]-F[l-1]) * (n/l) * (m/l); } return ans; } int main() { init(); int T;scanf("%d",&T); while (T--) { int n, m; scanf("%d%d",&n,&m); printf("%lld\n",calc(n, m)); } return 0; }
Yangzhichao
LV 10
@ 2025-12-24 18:43:06
- 1
