济南学习 Day2 T1 am

T1

题意：从1− n中找一些数乘起来使得答案是一个完全平方数，求这个完全平方数

最大可能是多少.

解析：

1、质因数分解

2、 1->n用质因数指数的相加的形式将1*n累乘起来

3、扫一遍指数为奇数的质因数都-1，偶数的不变

4、快速幂乘一遍，同时取模

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define ll long long

 #define mod 100000007

 using namespace std;

 const int N=5e8+;

 int prime[N],tot,n;

 bool check[N];

 void pre()

 {

     for(int i=;i<=n;i++)

     {

         if(!check[i]) prime[++tot]=i;

         for(int j=;j<=tot&&prime[j]*i<=n;j++)

         {

             check[prime[j]*i]=;

             if(i%prime[j]==) break;

         } 

     }

 }

 int main()

 {

     scanf("%d",&n);

     pre();

     memset(check,false,sizeof check );

     for(ll res,i=;i<=tot;i++)

     {

         res=;

         for(ll j=prime[i];j<=n;j*=(ll)prime[i]) res+=n/j;

         if(res&) check[prime[i]]=;

     }

     ll ans=;

     for(int i=;i<=n;i++)

       if(!check[i]) ans=ans*i%mod;

     printf("%I64d",ans);

     return ;

 }