H - Pairs Forming LCM

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

题目链接：https://cn.vjudge.net/contest/70017#problem/H

题目大意：给你一个数ｎ，让你在ｎ中找一对ａ，ｂ两个值且a<b，使得ａ和b的最大公倍数是ｎ。

题解：唯一分解定理，把每一个ａ和ｂ分解成以素数为因子的乘积（算数基本定理那样），需要取每一个素数因子的指数最大的那素因子然后相乘，使得到的数为ｎ。

例如a=a1^e1*a2^e2.........ax^ex        b= b1^z1*b2^z2...........bx^zx;       n=n1^y1*n2^y2...........nx^yx;

对于每一个素因子当ei=yi,zi可以选取０到yi的值所以有yi+1中情况，对于ｚi=yi，e1可以选取０到yi-1所以有yi中情况，所以对于每一个元素来说sum*=(2*yi+1);因为除了a=n,b=n的情况其他符合条件的情况都有２种，因为要选取a<=b的那种，所以最后(sum/2)+1;

代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 0x3f3f3f3fusing namespace std;const int MAX=1e7+5;
int prime[MAX/10];
bool vis[MAX+1];
int k;
void getprime()
{k=0;memset(vis,0,sizeof(vis));for(int i=2;i<=MAX;i++){if(!vis[i]) prime[++k]=i;for(int j=1;j<=k&&prime[j]*i<MAX;j++){vis[prime[j]*i]=1;if(i%prime[j]==0) break;}}
}int main()
{int T,m=0;long long int a,b;scanf("%d",&T);getprime();while(T--){++m;scanf("%lld",&a);long long int ans=1;for(b=1;b<=k&&a>=prime[b]*prime[b];b++){if(a%prime[b]==0){int cnt=0;while(a%prime[b]==0){a=a/prime[b];cnt++;}ans*=(cnt*2+1);}}if(a>1) ans=ans*3;printf("Case %d: %lld\n",m,ans/2+1);}return 0;
}

 

这篇关于H - Pairs Forming LCM的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---