凡科网站怎么做链接头像logo,怎么建设网站网页,网站建设职位名称,3d模型素材库Description 对于给出的n个询问#xff0c;每次求有多少个数对(x,y)#xff0c;满足a≤x≤b#xff0c;c≤y≤d#xff0c;且gcd(x,y) k#xff0c;gcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n#xff0c;接下来n行每行五个整数#xff0c;分别表示a、b、…Description 对于给出的n个询问每次求有多少个数对(x,y)满足a≤x≤bc≤y≤d且gcd(x,y) kgcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n接下来n行每行五个整数分别表示a、b、c、d、k Output 共n行每行一个整数表示满足要求的数对(x,y)的个数 Sample Input 2
2 5 1 5 1
1 5 1 5 2 Sample Output 14
3 HINT 100%的数据满足1≤n≤500001≤a≤b≤500001≤c≤d≤500001≤k≤50000 Source 题解 前置知识莫比乌斯反演 题目要求的是这个\[ ans \sum _ {ia}^b \sum _ {jc}^d [gcd(i,j)k] \] 我们可以利用二位前缀和的思想转化一下然后求这个\[ ans \sum _ {i1}^n \sum _ {j1}^m [gcd(i,j)k] \] 把\(k\)除掉\[ ans \sum _ {i1}^{\lfloor \frac{n}{k} \rfloor} \sum _ {j1}^{\lfloor \frac{m}{k} \rfloor} [gcd(i,j)1] \] 然后对于后面的\(gcd\)莫比乌斯反演下即\[ \sum _{d|n} \mu(d) [ n1 ] \] 带进去得\[ ans \sum _ {i1}^{\lfloor \frac{n}{k} \rfloor} \sum _ {j1}^{\lfloor \frac{m}{k} \rfloor} \sum _{d|i\d|j} \mu(d) \] 然后交换下枚举顺序先枚举\(d\)得\[ \begin {align} ans \sum _d\mu(d) \sum _{i1}^{\lfloor \frac{n}{kd} \rfloor} \sum _{j1}^{\lfloor \frac{m}{kd} \rfloor} 1 \\ \sum _d\mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \\ \end {align} \] 然后线筛下\(\mu\)整除分块下就做完了。 这里最好是把\(n\)和\(m\)分别除以\(k\)后在整除分块否则亲测会慢一倍虽然\(bzoj\)心情好的话卡时限能过。。 #includebits/stdc.h
using namespace std;#define int long long void read(int x) {x0;int f1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) f-f;for(;isdigit(ch);chgetchar()) xx*10ch-0;x*f;
}void print(int x) {if(x0) putchar(-),x-x;if(!x) return ;print(x/10),putchar(x%1048);
}
void write(int x) {if(!x) putchar(0);else print(x);putchar(\n);}const int maxn 5e410;int mu[maxn],pri[maxn],vis[maxn],tot,T;void sieve() {mu[1]1;for(int i2;imaxn;i) {if(!vis[i]) pri[tot]i,mu[i]-1;for(int j1;jtoti*pri[j]maxn;j) {vis[i*pri[j]]1;if(!(i%pri[j])) {mu[i*pri[j]]0;break;}else mu[i*pri[j]]-mu[i];}}for(int i1;imaxn;i) mu[i]mu[i]mu[i-1];
}int calc(int n,int m,int k) {int d1,ans0;n/k,m/k;while(dndm) {int pred;dmin(n/(n/d),m/(m/d));ans(n/d)*(m/d)*(mu[d]-mu[pre-1]);d;}return ans;
}signed main() {sieve();read(T);for(int i1,a,b,c,d,k;iT;i) {read(a),read(b),read(c),read(d),read(k);write(calc(b,d,k)-calc(b,c-1,k)-calc(a-1,d,k)calc(a-1,c-1,k));}return 0;
}转载于:https://www.cnblogs.com/hbyer/p/10052719.html
