2 条题解
-
0
#include <bits/stdc++.h> #define LL long long using namespace std; const int N=1e5; 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<=N;i++)for(int j=i;j<=N;j+=i) F[j]+=mu[j/i]*i; for(int i=1;i<=N;i++)F[i]+=F[i-1]; } LL calc(LL n,LL m) { LL ans=0; for(LL 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 2*ans-n*m; } int main() { init(); LL n,m;scanf("%lld%lld",&n,&m);if(n>m)swap(n,m); printf("%lld\n",calc(n,m)); return 0; } -
0
#include<bits/stdc++.h> #define LL long long using namespace std; const int N=1e5; 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<=N;i++)for(int j=i;j<=N;j+=i) F[j]+=mu[j/i]*i; for(int i=1;i<=N;i++)F[i]+=F[i-1]; } LL calc(LL n,LL m) { LL ans=0; for(LL 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 2*ans-n*m; } int main() { init(); LL n,m;scanf("%lld%lld",&n,&m);if(n>m)swap(n,m); printf("%lld\n",calc(n,m)); return 0; }
- 1
信息
- ID
- 3670
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 7
- 已通过
- 5
- 上传者