hdu4479 （数学题）（算术基本定理）

题目大意

给定一个三元组$(x,y,z)$的$gcd$和$lcm$，求可能的三元组的数量是多少，其中三元组是的具有顺序的

其中$gcd$和$lcm$都是32位整数范围之内

由算术基本定理可以得知：

如果$k=gcd(m,n) $则$ k_p=min(m_p,n_p)$

如果$k=lcm(m,n)$则$k_p=max(m_p,n_p)$

那么我们可以把每个质因数分开讨论，因为三元组是有序的，所以我们考虑每两个数成为gcd和lcm的，另一个数在$(p_gcd,p_lcm)$之间，那么这种时候就是$6×（r−l−1）$,然后考虑有两个点在端点的情况，因为是对称的，所以最终答案就是$6×(r−l+1)+3+3=6×(r−l)$

然后求解就可以

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<map>

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 1e6+1e2;

int g,l;

map<int,int> mpg,mpl;

int pg[maxn],pl[maxn];

int t;

int tmp=0;

int tmp1=0;

void count(int x)

{

	int n=x;

	for (int i=2;i*i<=x;i++)

	{

		if (n%i==0)

		{

			pg[++tmp]=i;

		}

		while (n%i==0)

		{

			n/=i;

			mpg[i]++;

		}

	}

	if (n>1) mpg[n]=1;

	pg[++tmp]=n;

}

void count1(int x)

{

	int n=x;

	for (int i=2;i*i<=x;i++)

	{

		if (n%i==0)

		{

			pl[++tmp1]=i;

		}

		while (n%i==0)

		{

			n/=i;

			mpl[i]++;

		}

	}

	if (n>1) mpl[n]=1;

	pl[++tmp1]=n;

}

int ans;

int main()

{

  cin>>t;

  while (t--)

  {

  	mpg.clear();

  	mpl.clear();

  	tmp=0;

  	tmp1=0;

  	g=read(),l=read();

  	count(g);

  	count1(l);

  	bool flag=true;

  	ans=1;

  	for (int i=1;i<=tmp;i++)

  	{

  		if (mpg[pg[i]]>mpl[pg[i]]) {

  		  flag=false;

			cout<<0<<endl;

		  }

	  }

	if (!flag) continue;

	for (int i=1;i<=tmp1;i++)

	{

		int cnt = mpl[pl[i]]-mpg[pl[i]];

		if (cnt==0) ans=ans*1;

		else {

			ans=ans*cnt*6;

		}

	}

	cout<<ans<<endl;

  }

  return 0;

}

巴特西

hdu4479 （数学题）（算术基本定理）

最新文章

热门文章