SPOJ-PGCD Primes in GCD Table

题目链接：https://vjudge.net/problem/SPOJ-PGCD

题目大意：

　　给定 \(N\) 和 \(M\)，求满足 \((1 \le x \le N), (1 \le y \le M)\)，且 \(gcd(x,y)\) 为素数的 \((x,y)\) 的对数。

知识点：　　莫比乌斯反演

解题思路：

　　设 \(g(p)\) 表示满足 \((1 \le x \le N), (1 \le y \le M)\)，且 \(gcd(x,y) = p\) 的 \((x,y)\) 的对数。直接求 \(g(p)\) 是不可行的，其时间复杂度为 \(O(NM)\).

　　再设 \(f(p)\) 表示满足 \((1 \le x \le N), (1 \le y \le M)\)，且 \(p|gcd(x,y)\) 的 \((x,y)\) 的对数，易知 \(f(p)=(N/p)*(M/p)\)。且不难推出 \(f(n) = \sum \limits_{n|d} g(d)\).　　　　\((1)\)

　　莫比乌斯反演公式：若满足 \(F(n) = \sum \limits_{n|d} f(d)\)，则有 \(f(n) = \sum \limits_{n|d} \mu(\frac{d}{n})F(d)\).

　　将其代入式 \((1)\) 得：

　　\(g(n) = \sum \limits_{n|d} \mu(\frac{d}{n})f(d) = \sum \limits_{n|d} \mu(\frac{d}{n})(N/d)(M/d)\)　　\((2)\)

　　最终的答案为（\(p\) 代表质数）：

　　\(\sum \limits_{p} g(p) = \sum \limits_{p} \sum \limits_{p|d} \mu(\frac{d}{p})(N/d)(M/d)\)

　　　　　　\(= \sum \limits_{d}^{min(M,N)} (N/d)(M/d) \sum \limits_{p|d} \mu(\frac{d}{p})\)　　\((3)\)

第二个求和函数可以预处理，枚举每一个质数，更新对应的前缀和。

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int maxn = 1e7+;

 bool check[maxn];

 int prime[maxn],Mobius[maxn];

 int tot;

 int u[maxn];

 void init(){

     Mobius[]=;

     tot=;

     for(int i=;i<maxn;i++){

         if(!check[i]){

             prime[tot++]=i;

             Mobius[i]=-;

         }

         for(int j=;j<tot&&i*prime[j]<maxn;j++){

             check[i*prime[j]]=true;

             if(i%prime[j]==){

                 Mobius[i*prime[j]]=;

                 break;

             } else

                 Mobius[i*prime[j]]=-Mobius[i];

         }

     }

     for(int i=;i<tot;i++){

         for(int j=prime[i];j<maxn;j+=prime[i]){

             u[j]+=Mobius[j/prime[i]];   // u[j] 代表分子为 j(对应式3中的d) 的和函数的值

         }

     }

     for(int i=;i<maxn;i++) u[i]+=u[i-];   //处理出前缀和

 }

 int main(){

     init();

     int t,n,m;

     scanf("%d",&t);

     while(t--){

         LL ans=;

         int last;

         scanf("%d%d",&n,&m);

         for(int i=;i<=min(n,m);i=last+){

             last=min(n/(n/i),m/(m/i));  // [i,last] 这一段的 u[] 对应 (N/d)(M/d) 相等，不难用实验验证

             ans+=(LL)(n/i)*(m/i)*(u[last]-u[i-]);

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

SPOJ-PGCD Primes in GCD Table

最新文章

热门文章