题目大意：给出一个数，判断其是否有含有平方因子

解题思路：1）10^18这是一个很大的数据，暴力是绝对不可行的。
              2）如果其含有平方因子，则有n=a^2*b，这里的n<=10^18，所以a,b中必定有一个是小于10^6~。
              3）筛10^6以内的素数，然后用n去除以这些质数的平方，如果能除，返回NO，否则，则看是否能够除以这个素数。
              4）10^6以内的素数除光了，如果是1返回YES              
              5）剩下的也就只有三种可能，素数，素数的平方和，或者两个素数的积。
                     （证明：首先，剩下的肯定是比10^6大的素数，这个是毫无疑问的，而且这些素数因子的个数不可能超过3个，所以只有以上三种情况）
              6）是两个素数的积返回NO，其他的YES

代码：
 1#include <cstdio>
 2#include <cstdlib>
 3#include <cmath>
 4#include <iostream>
 5#include <algorithm>
 6
 7using namespace std;
 8
 9int prime[80000];
10bool p[1000002];
11
12void PRIME(int M)
13{
14    int i,i2,k;
15    for(i=0;i<=M;i+=2){ p[i]=0; }
16    for(i=1;i<=M;i+=2){ p[i]=1; }
17    p[2]=1;
18    p[1]=0;
19    for(i=3;i<=1000;i+=2)
20    {
21        if(p[i]==1)
22          {
23              i2=i+i;
24              k=i*i;
25              while(k<=M)
26              {
27                  p[k]=0;
28                  k+=i2;
29              }
30           }
31     }
32     prime[1]=2;
33     k=1;
34     for(i=3;i<=M;i+=2)
35        if(p[i])   prime[++k]=i;
36     prime[0]=k;
37     return ;
38}
39
40
41int Int(long long n)
42{
43    int i,s,k;
44    long long d,e;
45    k=0;
46    for(i=1;i<=prime[0];i++)
47    {
48       s=0;
49       while(n%prime[i]==0)
50         {
51             s++;
52             n/=prime[i];
53         }
54
55       if(s>1) return -1;
56       if(n==1) return 1;
57       if(n/prime[i]<prime[i]) return 1;
58     }
59     d=(long long)sqrt((double)n);
60     d--;
61     while(1)
62     {
63         e=d*d;
64         if(e==n)return -1;
65         if(e>n)break;
66         d++;
67     }
68    return 1;
69 }
70
71int main()
72 {
73   int T,i,k;
74   long long N,d;
75   PRIME(1000000);
76   scanf("%d",&T);
77   for(i=1;i<=T;i++)
78    {
79      scanf("%I64d",&N);
80      k=Int(N);
81      if(k==1) printf("Case %d: Yes\n",i);
82      else  printf("Case %d: No\n",i);
83     }
84    return 0;
85}
86
87