YYHSOI模拟赛题解（T4完全平方数）

题目描述

一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数（Pefect Sqaure），也称平方数。

小A认为所有的平方数都是很perfect的~

于是他给了小B一个任务：用任意个不大于n的不同的正整数相乘得到完全平方数，并且小A希望这个平方数越大越好。

请你帮助小B告诉小A满足题意的最大的完全平方数。

输入

输入文件名为number.in

输入仅 1行，一个数n。

输出

输出文件名为number.out

输出仅1行，一个数表示答案。由于答案可以很大，所以请输出答案对100000007取模后的结果。

样例输入

【输入输出样例1】

number.in

number.out

144

【输入输出样例解释1】

144=2×3×4×6，是12的完全平方。

样例输出

【输入输出样例2】

number.in

number.out

5184

【输入输出样例解释2】

5184=3×4×6×8×9，是72的完全平方。

提示

【数据范围】

对于20%的数据，0<n≤100；

对于50%的数据，0<n≤5,000；

对于70%的数据，0<n≤100,000；

对于100%的数据，0<n≤5,000,000。

这一道题目，我一看就觉得是质因数分解，但是由于数据范围是500W，所以对于一般的筛法就不可行了，所以这一道题目需要用到欧拉线性筛来筛出所有的质数。但是筛完后对于分解质因数仍然没有帮助。然后我就想到了初中数学所学过的，如果对于一个范围内的数质因数分解后存在几个P（P为质数），我们有一个求和式，我就把这个用上去了。然后这道题目的时间复杂度就变成了约为2000W的一个算法

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 int N;
10 long long Mod=100000007;
11 bool flag[5000005];
12 int p[5000005];
13 long long s[5000005];
14 int num;
15 int top=0;
16 int q[5000005];
17 
18 long long mul(int a,long long b,long long Mod)
19 {
20     long long tmp=1;
21     long long A=(long long) a;
22     while (b)
23     {
24         if (b & 1) tmp=((tmp % Mod) * (A % Mod)) % Mod;
25         A=(A % Mod) * (A % Mod) % Mod;
26         b=b >> 1;
27     }
28     return tmp;
29 }
30 
31 int main()
32 {
33     scanf("%d",&N);
34     for (int i=2; i<=N; i++)
35     {
36         if (! flag[i])
37         {
38             p[++num]=i;
39         }
40         for (int j=1; p[j] * i <= N && j<=num; j++)
41         {
42             flag[p[j]*i]=1;
43             if (i % p[j] == 0) break;
44         }
45     }
46     /*for (int i=2; i<=N; i++)
47     {
48         if (! flag[i])
49         {
50             continue;
51         }
52         int X=i;
53         for (int j=1; j<=num; j++)
54         {
55             while (X % p[j] == 0)
56             {
57                 s[p[j]]++;
58                 X=X / p[j];
59             }
60             if (X == 0) break;
61         }
62     }*/
63     for (int i=1; i<=num; i++)
64     {
65         for (long long j=p[i]; j<= N; j*=p[i])
66         {
67             s[p[i]]+=(long long) N / j;
68         }
69     }
70     long long ans=1;
71     for (int j=1; j<=num; j++)
72     {
73         //printf("%d %d\n",p[j],s[p[j]]);
74         int i=p[j];
75         long long b=s[i];
76         if (b & 1) b--;
77         if (b == 0) continue;
78         long long tmp=mul(i,b,Mod);
79         ans=(ans % Mod) * (tmp % Mod) % Mod;
80     }
81     printf("%lld\n",ans);
82     return 0;
83 }

Show My Ugly Code