东莞网站建,wordpress 进销存,软装设计培训,网站销售的优势P2522 HAOI2011
题意
对于给出的n个询问#xff0c;每次求有多少个数对(x,y)(x,y)(x,y)#xff0c;满足a≤x≤ba≤x≤ba≤x≤b#xff0c;c≤y≤dc≤y≤dc≤y≤d#xff0c;且gcd(x,y)kgcd(x,y) kgcd(x,y)k#xff0c;gcd(x,y)gcd(x,y)gcd(x,y)函数为xxx和yyy的最大公约…P2522 HAOI2011
题意
对于给出的n个询问每次求有多少个数对(x,y)(x,y)(x,y)满足a≤x≤ba≤x≤ba≤x≤bc≤y≤dc≤y≤dc≤y≤d且gcd(x,y)kgcd(x,y) kgcd(x,y)kgcd(x,y)gcd(x,y)gcd(x,y)函数为xxx和yyy的最大公约数.
题解
即求式子∑xab∑ycd[gcd(x,y)k]\sum_{xa}^b\sum_{yc}^d[gcd(x,y)k]∑xab∑ycd[gcd(x,y)k].
记f(n,m)∑x1n∑y1m[gcd(x,y)k]f(n,m)\sum_{x1}^n\sum_{y1}^m[gcd(x,y)k]f(n,m)∑x1n∑y1m[gcd(x,y)k]
根据二维前缀和公式,可以将式子转换成:
∑xab∑ycd[gcd(x,y)k]f(b,d)f(a−1,c−1)−f(a−1,d)−f(b,c−1)\sum_{xa}^b\sum_{yc}^d[gcd(x,y)k]f(b,d)f(a-1,c-1)-f(a-1,d)-f(b,c-1)∑xab∑ycd[gcd(x,y)k]f(b,d)f(a−1,c−1)−f(a−1,d)−f(b,c−1)
因此我们只要能得到f(n,m)f(n,m)f(n,m)的计算方法即可.
求f(n,m)f(n,m)f(n,m)的套路非常明显:莫比比乌斯反演
由于∑k∣d∑x1n∑y1m[gcd(x,y)d]⌊nk⌋⌊mk⌋\sum_{k|d}\sum_{x1}^n\sum_{y1}^m[gcd(x,y)d] \lfloor \frac{n}{k} \rfloor \lfloor \frac{m}{k} \rfloor∑k∣d∑x1n∑y1m[gcd(x,y)d]⌊kn⌋⌊km⌋.
反演得到f(n,m)∑k∣dμ(dk)⌊nd⌋⌊md⌋f(n,m)\sum_{k|d}\mu(\frac{d}{k})\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloorf(n,m)∑k∣dμ(kd)⌊dn⌋⌊dm⌋
令td/kt d/ktd/k.
f(n,m)∑t1n/dμ(t)⌊nkt⌋⌊mkt⌋f(n,m)\sum_{t1}^{n/d}\mu(t)\lfloor \frac{n}{kt} \rfloor \lfloor \frac{m}{kt} \rfloorf(n,m)∑t1n/dμ(t)⌊ktn⌋⌊ktm⌋
对上式子进行分块计算,可以将时间复杂度从O(n)O(n)O(n)降至O(n)O(\sqrt{n})O(n).
总结
对于形如f(x)∑x∣dμ(dx)g(⌊nd⌋)f(x)\sum_{x|d}\mu(\frac{d}{x})g(\lfloor \frac{n}{d} \rfloor)f(x)∑x∣dμ(xd)g(⌊dn⌋)这样的式子,我们都可以用td/xtd/xtd/x代换后数论分块进行加速.
f(x)∑t1n/xμ(t)g(⌊nxt⌋)f(x)\sum_{t1}^{n/x}\mu(t)g(\lfloor \frac{n}{xt} \rfloor)f(x)∑t1n/xμ(t)g(⌊xtn⌋)
时间复杂度从O(n)O(n)O(n)降至O(n)O(\sqrt{n})O(n).
代码
#include iostream
#include algorithm
#include cstring
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)const int N 50000;int prime[N10],zhi[N10],mu[N10],pcnt;void sieve() {zhi[1] mu[1] 1;for(int i 2;i N;i) {if(!zhi[i]) {mu[i] -1;prime[pcnt] i;}for(int j 0;j pcnt prime[j]*i N;j) {zhi[i*prime[j]] 1;if(i % prime[j] 0) {mu[i*prime[j]] 0;break;}else mu[i*prime[j]] -mu[i];}}for(int i 1;i N;i) mu[i] mu[i-1];
}
int a,b,c,d,k,T;
int calc(int n,int m) {int ans 0;int lim std::min(n/k,m/k);for(int i 1,nx1,nx2,nxt;i lim;inxt1) {nx1 n/(n/i);nx2 m/(m/i);nxt nx1nx2?nx2:nx1;ans (mu[nxt]-mu[i-1])*(n/i/k)*(m/i/k);}return ans;
}
int main() {std::ios::sync_with_stdio(false);sieve();std::cin T;while(T--) {std::cin a b c d k;int ans calc(b,d)calc(a-1,c-1)-calc(a-1,d)-calc(b,c-1);std::cout ans std::endl;}return 0;
}
