首页 > ACM题库 > HDU-杭电 > HDU 3826-Squarefree number-数论-[解题报告]HOJ
2015
04-13

HDU 3826-Squarefree number-数论-[解题报告]HOJ

Squarefree number

问题描述 :

In mathematics, a squarefree number is one which is divisible by no perfect squares, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 3^2. Now you need to determine whether an integer is squarefree or not.

输入:

The first line contains an integer T indicating the number of test cases.
For each test case, there is a single line contains an integer N.

Technical Specification

1. 1 <= T <= 20
2. 2 <= N <= 10^18

输出:

The first line contains an integer T indicating the number of test cases.
For each test case, there is a single line contains an integer N.

Technical Specification

1. 1 <= T <= 20
2. 2 <= N <= 10^18

样例输入:

2
30
75

样例输出:

Case 1: Yes
Case 2: No

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3826

算法分析:

对于2-10^18的任意一个数 都能转化成如下的形式  Squarefree number……等等 a,b,c,d都是质数

然后 

情况1  将输入的num 先从 2-10^6中的质数进行相除,有一个质数能连出两次以上 就输出no 

情况2  如果能整除 num=num/i 然后 如果 相除后num==1 输出yes

进行完一二操作后 本题中剩下的num这个数 (因为不存在1-10^6的质数) 最多只有两个质数 

情况3   只有两种结果 两个10^6-10^9 的质数相乘 或者只有一个质数 在10^6-10^18次方之间。  这样只要判断第一种结果是否是两个相同质数相乘的情况了~~

#include<stdio.h>
#include<math.h>
#include<string.h>
#define M 1100000
#define MIN 0.00001
int a[M],b[500000],flag;
int init()
{
    int i,j;
    memset(a,0,sizeof(a));
    for(i=2;i*i<=M;i++)
    {
        if(!a[i])
        {
            for(j=i*2;j<=M;j=j+i)
            {
               a[j]=1;
            }
        }
    }
    j=1;
    for(i=2;i<=M;i++)
    {
        if(!a[i])

        {
        b[j]=i;
         j++;
        }
    }
    return j;

}
void pd(double nu)
{
    double a;
    a=sqrt(nu);
    if(a-floor(a)<=MIN)
     flag=0;
     else
     flag=1;

}
int main()
{
    int n;
    scanf("%d",&n);
    int cs=0;
    int len=init();
    //printf("%d\n",len);
    while(n--)
    {
        cs++;
         __int64 num;
         int i;
         scanf("%I64d",&num);
         flag=0;
         for(i=1;i<len;i++)
         {

             int sum=0;
             while(num%b[i]==0)
             {
                 num/=b[i];
                 sum++;
             }
             if(sum>=2)
              {
                  flag=1;
                  break;
              }
         }
         if(flag==1)
         {printf("Case %d: No\n",cs);continue;}
        if(num==1)
        {printf("Case %d: Yes\n",cs);continue;}
              pd((double)num);
              if(flag==0)
          printf("Case %d: No\n",cs);
        else
        printf("Case %d: Yes\n",cs);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/nywsp/article/details/8241258


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的