首页 > 代码库 > 校队训练赛，同时也是HDU4497（数论：素数分解+组合数学）

校队训练赛，同时也是HDU4497（数论：素数分解+组合数学）

2024-07-21 12:14:16   218人阅读

一、题目

 

 

http://acm.hdu.edu.cn/showproblem.php?pid=4497

二、思路
将满足条件的一组x,z,y都除以G,得到x‘，y‘,z‘,满足条件gcd(x‘,y‘,x‘) = 1,同时lcm(x‘,y‘,x‘) = G/L.
特判，当G%L ！= 0 时，无解。
然后素数分解G/L，假设G/L = p1^t1 * p2^t2 *````* pn^tn。
满足上面条件的x,y,z一定为这样的形式。
x‘ = p1^i1 * p2^i2 *```* pn^in.
y‘ = p1^j1 * p2^j2 * ```*pn^jn.
z‘ = p1^k1 * p2^k2 * ```*pn^kn.
为了满足上面的条件，对于p1,一定有max(i1,j1,k1) = t1.min(i1,j1,k1) =0;则当选定第一个数为0，第二个数为t1时，第三个数可以为0-t1，又由于有顺序的，只有(0,t1,t1) 和(0,t1,0)这两种情形根据顺序只能产生三种结果，其他的由于三个数都不一样，一定能产生6种，所以最后产生了6*（t1-1）+3*2 = 6*t1种，根据乘法原理以及关于素数分解的唯一性，反过来，素数组合必然也是唯一的数，一共有6*t1 * 6*t2 *`````*6*tn种选法。

 三、代码

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>using namespace std;int p[100005];long long ans;int n;long long gcd(int x){    //int temp = int (sqrt(x) + 1);[如果按这样写，不按下面的写提交时就会出现“编译错误”！！！]    /*sqrt函数      功 能： 计算一个非负实数的平方根      函数原型： 在VC6.0中的math.h头文件的函数原型为double sqrt(double);*/    int temp=sqrt(x*1.0+0.5);    memset(p,0,sizeof(p));    for(int i = 2; i <= temp; i++)    {        while(x%i == 0)        {            x = x/i;            p[i]++;        }    }    if(x != 1) ans = 6;//如果b/a本身是素数    else ans = 1;     for(int i = 2; i <= temp; i++)    {        if(p[i])            ans *= p[i]*6;    }    return ans;}int main(){    int a,b;    scanf("%d",&n);    while(n--)    {        scanf("%d%d",&a,&b);        if(b%a != 0)            printf("0\n");        else        {            printf("%I64d\n",gcd(b/a));        }    }    return 0;}

四、训练赛的时候没有做出来，一直想着能不能用辗转相除法求三个数的最大公约数。，之后看了http://blog.csdn.net/tobewhatyouwanttobe/article/details/10285863的博客才明白。

后来，看了别人的思路，自己敲的时候，还是遇到了一些开始没想通的地方，不过，后来都解决了，并且标注到了程序里。

 

坦白说，这道题我原来做过类似的，当时做的时候就没大明白，后来解决之后，也没有回顾，更没有再练习相似的题，这是个教训，也值得反思！！！！！

校队训练赛，同时也是HDU4497（数论：素数分解+组合数学）


联系
我们