一个网站数据库,网站建设学多长时间,江西合创建设工程有限公司 网站,三明做网站很入门的数论函数题目。我还是wa了一发#xff08;爆long long 了#xff09; 对于每个位置x,y#xff0c;在他们和能量采集器中间的植物为gcd(x,y)-1#xff0c;【在他们之间说明斜率相同#xff0c;而和他们斜率相同的就是所有gcd(x/gcd(x,y),y/gcd(x,y))1的并且比他们小…很入门的数论函数题目。我还是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代码
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e55;
int prime[MAXN],phi[MAXN],sum[MAXN];
bool check[MAXN]; int tot;void pre()
{tot0; phi[1]1; sum[1]1;for(int i2;iMAXN;i){if(!check[i]){prime[tot]i; phi[i]i-1;}for(int j0;jtot prime[j]*iMAXN;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 limitmin(n,m);ll l,r;ll ans0;for(l1;llimit;lr1){rmin(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;
}
