P3455 [POI2007]ZAP-Queries

太阳不下山

题目描述
Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has alreadyfound out that whilst deciphering a message he will have to answer multiple queries of the form"for givenintegers aaa, bbb and ddd, find the number of integer pairs (x,y)(x,y)(x,y) satisfying the following conditions:
1≤x≤a1\le x\le a1≤x≤a,1≤y≤b1\le y\le b1≤y≤b,gcd(x,y)=dgcd(x,y)=dgcd(x,y)=d, where gcd(x,y)gcd(x,y)gcd(x,y) is the greatest common divisor of xxx and yyy".
Byteasar would like to automate his work, so he has asked for your help.
TaskWrite a programme which:
reads from the standard input a list of queries, which the Byteasar has to give answer to, calculates answers to the queries, writes the outcome to the standard output.
FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。

输入输出格式
输入格式：
The first line of the standard input contains one integer nnn (1≤n≤50 0001\le n\le 50\ 0001≤n≤50 000),denoting the number of queries.
The following nnn lines contain three integers each: aaa, bbb and ddd(1≤d≤a,b≤50 0001\le d\le a,b\le 50\ 0001≤d≤a,b≤50 000), separated by single spaces.
Each triplet denotes a single query.
输出格式：
Your programme should write nnn lines to the standard output. The iii'th line should contain a single integer: theanswer to the iii'th query from the standard input.

输入输出样例

输入样例#1：

2
4 5 2
6 4 3

输出样例#1：

3
2

Solution：
本题莫比乌斯反演板子题。
题意就是求$\sum_\limits{i=1}^{i\leq n}\sum_\limits{j=1}^{j\leq m} gcd(i,j)==d$。
令$f(n)$表示满足约束条件的且$gcd(i,j)=n$的个数，令$F(n)$表示满足约束条件的且$n|gcd(i,j)$的个数。
于是有$F(n)=\sum_\limits{n|d} {f(d)}$，这个式子显然可以反演，得到$f(n)=\sum_\limits{n|d} {\mu(\frac{d}{n})*F(d)}$。
又因为对于数$x$，显然$n$中含有$\frac{n}{x}$个$x$的倍数，同理$m$中有$\frac{m}{x}$个，所以$F(x)=\frac{n}{x}*\frac{m}{x}$。
则原式变为$f(d)=\sum_\limits{d|k}^{k\leq min(n,m)}{\mu(\frac{k}{d})\frac{n}{k}\frac{m}{k}}$。
令$t=\frac{k}{d}$，则原式变为$f(d)=\sum_\limits{t=1}^{\frac{min(n,m)}{d}}{\frac{n}{td}\frac{m}{td}}$，对于$\lfloor \frac{n}{td}\rfloor \lfloor \frac{m}{td} \rfloor$直接数论分块求就好了，所以还得预处理下$\mu$的前缀和。
时间复杂度$O(q\sqrt n)$。
代码：

/*Code by 520 -- 9.10*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=50005;
int n,a,b,d,mu[N],prime[N],cnt;
bool isprime[N];
int gi(){
  int a=0;char x=getchar();
  while(x<'0'||x>'9')x=getchar();
  while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+(x^48),x=getchar();
  return a;
}
il void pre(){
  mu[1]=1;
  For(i,2,50000){
    if(!isprime[i]) mu[i]=-1,prime[++cnt]=i;
    for(RE int j=1;j<=cnt&&prime[j]*i<=50000;j++){
      isprime[i*prime[j]]=1;
      if(i%prime[j]==0) break;
      mu[i*prime[j]]=-mu[i];
    }
  }
  For(i,1,50000) mu[i]+=mu[i-1];
}
int solve(){
  if(a>b) swap(a,b);
  a/=d,b/=d;
  int pos=0,ans=0;
  for(int i=1;i<=a;i=pos+1){
    pos=min(a/(a/i),b/(b/i));
    ans+=(mu[pos]-mu[i-1])*(a/i)*(b/i);
  }
  return ans;
}
int main(){
  pre();
  n=gi();
  while(n--){
    a=gi(),b=gi(),d=gi();
    printf("%d\n",solve());
  }
  return 0;
}

PS：～蒟蒻写博客不易，转载请注明出处，万分感谢！～

[C++] P3455 [POI2007]ZAP-Queries

相关帖子

Grouping策略，并行度，消息的可靠处理机制

太阳不下山 LV4