新能源网站建设哪家好,创建网站的流程有哪些,优惠券的网站怎么做,公司部门介绍正题 题目大意
求∑iab∑jcd(gcd(i,j)k)\sum_{ia}^b\sum_{jc}^d(gcd(i,j)k)ia∑bjc∑d(gcd(i,j)k) 解题思路
定义 f(i)∑i1n∑j1m(gcd(i,j)i)f(i)\sum_{i1}^n\sum_{j1}^m(gcd(i,j)i)f(i)i1∑nj1∑m(gcd(i,j)i) 然后计算f利用容斥计算答案
之后我们考虑如何计算 F(i)…正题 题目大意
求∑iab∑jcd(gcd(i,j)k)\sum_{ia}^b\sum_{jc}^d(gcd(i,j)k)ia∑bjc∑d(gcd(i,j)k) 解题思路
定义 f(i)∑i1n∑j1m(gcd(i,j)i)f(i)\sum_{i1}^n\sum_{j1}^m(gcd(i,j)i)f(i)i1∑nj1∑m(gcd(i,j)i) 然后计算f利用容斥计算答案
之后我们考虑如何计算 F(i)∑dd∣if(i)F(i)\sum^{d|i}_df(i)F(i)d∑d∣if(i) 显然可得出 F(i)⌊ni⌋⌊mi⌋F(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloorF(i)⌊in⌋⌊im⌋ 然后莫比乌斯反演一下 f(i)∑d∣iμ(dk)F(d)f(i)\sum_{d|i}\mu(\frac{d}{k})F(d)f(i)d∣i∑μ(kd)F(d) f(i)∑d∣iμ(dk)⌊nd⌋⌊md⌋f(i)\sum_{d|i}\mu(\frac{d}{k})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloorf(i)d∣i∑μ(kd)⌊dn⌋⌊dm⌋ 时间复杂度降低到O(n)O(n)O(n) 之后我们可以发现⌊nd⌋\lfloor\frac{n}{d}\rfloor⌊dn⌋只有2n2\sqrt n2n种取值那么⌊ni⌋⌊mi⌋\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor⌊in⌋⌊im⌋最多就有2(nm)2(\sqrt n\sqrt m)2(nm)种取值我们可以直接计算这个范围内莫比乌斯函数的前缀和然后直接O(min{n,m})O(\sqrt {min\{n,m\}})O(min{n,m})计算答案 code
// luogu-judger-enable-o2
#includecstdio
#includealgorithm
#define N 50000
#define ll long long
using namespace std;
ll miu[N10],c,d,a,b,k,t;
bool v[N10];
void sumul()
{for(ll i1;iN;i) miu[i]1,v[i]0;for(ll i2;iN;i){if(v[i]) continue;miu[i]-1;for(ll j2*i;jN;ji){v[j]1;if((j/i)%i0) miu[j]0;else miu[j]*-1;}}for(ll i1;iN;i)miu[i]miu[i-1];
}
ll ask(ll n,ll m)
{if(nm) swap(n,m);ll last,re0;n/k;m/k;for(ll i1;in;ilast1){lastmin(n/(n/i),m/(m/i));re(n/i)*(m/i)*(miu[last]-miu[i-1]);}return re;
}
int main()
{sumul();scanf(%lld,t);for(ll i1;it;i){scanf(%lld%lld%lld%lld%lld,a,b,c,d,k);printf(%lld\n,ask(b,d)ask(a-1,c-1)-ask(a-1,d)-ask(b,c-1));}
}
