hdu 3826

Squarefree number

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1984 Accepted Submission(s): 526

Problem Description

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.

Input

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

Output

For each test case, output the case number first. Then output "Yes" if N is squarefree, "No" otherwise.

Sample Input

Sample Output

Case 1: Yes

Case 2: No

Author

hanshuai

采用如果素因子超过2次，NO。这个很好理解。

这样还是会超时。10^18次方，最坏的情况下10^9次方。

但是，我们只需要枚举10^6内的素数就可以。为什么？

假如n 有(10^6,10^9)的一个素因子平方构成 ,不在10^6范围，但是可能直接开方判断即可。

还有假如是(10^,10^9)的一个素因子平方*a构成，则a必在10^6内。不然数字就超过10^18次方了。

我们用[1,10^6]内的素数，刷一遍的时候，就可能除去a，然后又可以开方，直接判断就行。

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<math.h>
 6 using namespace std;
 7 typedef __int64 LL;
 8 
 9 bool s[1000002];
10 LL prime[78500],len;
11 void init()
12 {
13     int i,j;
14     len=0;
15     memset(s,false,sizeof(s));
16     for(i=2;i<=1000000;i++)
17     {
18         if(s[i]==true)continue;
19         prime[++len]=i;
20         for(j=i*2;j<=1000000;j=j+i)
21             s[j]=true;
22     }
23 }
24 LL Euler(LL n)
25 {
26     LL i,num;
27     for(i=1;prime[i]*prime[i]<=n && i<=len;i++)
28     {
29         if(n%prime[i]==0)
30         {
31             num=0;
32             while(n%prime[i]==0)
33             {
34                 n=n/prime[i];
35                 num++;
36                 if(num>=2) return 0;
37             }
38         }
39     }
40     return n;
41 }
42 int main()
43 {
44     init();
45     int T,t;
46     LL n;
47     scanf("%d",&T);
48     for(t=1;t<=T;t++)
49     {
50         scanf("%I64d",&n);
51         LL ans = Euler(n);
52         if(ans==0)
53         {
54             printf("Case %d: No
",t);
55         }
56         else
57         {
58             LL cur=(LL)sqrt(ans*1.0);
59             if(cur*cur==ans)printf("Case %d: No
",t);
60             else printf("Case %d: Yes
",t);
61         }
62     }
63     return 0;
64 }