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 ;
}

最新文章

  1. UE4 代码编写细节:静态变量
  2. hdu1241 Oil Deposits
  3. Android 利用Service实现下载网络图片至sdk卡
  4. 再论App的安全性
  5. rails中ActionController::InvalidAuthenticityToken解决办法
  6. Nginx之负载均衡
  7. 这是我用Microsoft Word 2010 直接发布的测试用博客
  8. 如何写angularJS模块
  9. eclipse 导入tomcat7源码
  10. mysql -- 备忘
  11. 【转】C++静态库与动态库
  12. oracle case when及decode的用法
  13. LINQ之道
  14. mysql数据库的查询,添加,删除,还原,备份
  15. 浅谈文件断点续传和WebUploader的基本结合
  16. CSS3圆角详解(border-radius)
  17. Java连接MySQL数据库详细教程(附网盘下载地址)
  18. 使用babel将ES6编译成ES5
  19. python作业学员管理系统(第十二周)
  20. Gradle for Android 翻译 -1

热门文章

  1. JavaWeb学习总结
  2. IIS问题汇总
  3. NET开发必备工具之-LINQPad
  4. EMS电子面单接口对接使用-免费版
  5. Amazon 开始接受 Windows 礼品卡预订
  6. [MySQL] 数据统计 —— 按周,按月,按日分组统计数据
  7. 【Android 界面效果14】RelativeLayout里常用的位置属性
  8. Vmware出现报错The VMware Authorization Service is not running.之后无法上网解决
  9. 监控服务器JVM内存运行
  10. 【转】ConcurrentHashMap完全解析(JDK6/7、JDK8)