spoj PGCD - Primes in GCD Table

2024-03-02 08:48

文章标签 table primes gcd spoj pgcd

本文主要是介绍spoj PGCD - Primes in GCD Table，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目链接：

题目链接：

https://www.spoj.com/problems/PGCD/
原来spoj知道题号不行啊。。要知道题的名字才行。。。然后改掉网址后面的题号就阔以了。。。
题意：就是求gcd(x,y)=质数的个数
做过莫比乌斯的模板的就很清楚，不就是求f(2)+f(3)+f(5)+…+f§么？如果真是这样，那就是一道模板题，就没有什么意思了，果然，暴力这样求T掉了，嗯~不错不错

我们把相同的F(n)的mu写在一起，就是F(n)*(mu(x1)+mu(x2)+…) 这样，阔以发现，x1,x2…都是n的质因子，然后就用一个Cnt[i]来记录 i 的所以质因子的莫比乌斯函数和，又因为要用到一段一段的，所以就用的是前缀和的那个套路就行了~

打个F的表，前面的系数mu 就不写了

在这里插入图片描述

#include"iostream"
#include"cstring"
#include"vector"
typedef long long LL;
using namespace std;
const int maxn=1e7+5;
char mu[maxn];
int Smu[maxn];
vector<int>prime;
bool vis[maxn];
int Cnt[maxn];//Cnt[i]表示i所有因子的mu的和 
int sum[maxn];
void Init(int n)
{memset(vis,1,sizeof(vis));mu[1]=1;Smu[1]=1;for(int i=2; i<=n; i++){if(vis[i]){prime.push_back(i);mu[i]=-1;}for(int j=0; j<prime.size()&&i*prime[j]<=n; j++){vis[i*prime[j]]=0;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}else mu[i*prime[j]]=-mu[i];}Smu[i]=Smu[i-1]+mu[i];}for(int i=1;i<=n;i++){if(mu[i]==0)continue;for(int j=0;j<prime.size();j++){if((LL)i*prime[j]>n)break;Cnt[i*prime[j]]+=mu[i]; }}for(int i=1;i<=n;i++)sum[i]=sum[i-1]+Cnt[i];
}
long long F(int d,int n,int m)
{return (long long)(n/d)*(m/d);
}
int main()
{Init(maxn-5);int N,M,T;cin>>T;while(T--){cin>>N>>M;LL ans=0;int n=min(N,M);for(int i=1,j;i<=n;i=j+1){j=min(N/(N/i),M/(M/i));ans+=1LL*(sum[j]-sum[i-1])*F(i,N,M);}cout<<ans<<endl;}
}