很入门的数论函数题目。我还是wa了一发（爆long long 了） 对于每个位置x,y，在他们和能量采集器中间的植物为gcd(x,y)-1，【在他们之间说明斜率相同，而和他们斜率相同的就是所有gcd(x/gcd(x,y),y/gcd(x,y))=1的并且比他们小的，就是gcd(x,y)-1个】，所以x,y位置损失的能量为2gcd(x,y)-1，然后对所有的gcd求和，问题就转换成了如何快速的对该区域内的所有gcd求和，如果暴力的话复杂度应该是O(n2logn)级别的，肯定会超时。对于这种不能暴力求和的题目，我们就要想到用数论函数这个强大的工具。因为求的是gcd的值，我们根据卷积式欧拉函数卷积恒等函数等于单位函数，将gcd的值看作单位函数的值，然后再求和。再将求和公式化简后用除法分块处理。
AC代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<cmath> #include<ctime> #include<climits> #include<queue> #include<vector> #include<set> #include<map> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=1e5+5; int prime[MAXN],phi[MAXN],sum[MAXN]; bool check[MAXN]; int tot; void pre() { tot=0; phi[1]=1; sum[1]=1; for(int i=2;i<MAXN;i++) { if(!check[i]) { prime[tot++]=i; phi[i]=i-1; } for(int j=0;j<tot && prime[j]*i<MAXN;j++) { check[prime[j]*i]=true; if(i%prime[j]) phi[prime[j]*i]=(prime[j]-1)*phi[i]; else { phi[prime[j]*i]=prime[j]*phi[i]; break; } } sum[i]=sum[i-1]+phi[i]; } } int main() { pre(); ll n,m; scanf("%lld%lld",&n,&m); ll limit=min(n,m); ll l,r; ll ans=0; for(l=1;l<=limit;l=r+1) { r=min(n/(n/l),m/(m/l)); ans+=(ll)(sum[r]-sum[l-1])*(n/l)*(m/l); } printf("%lld\n",2*ans-n*m); return 0; }