济南学习 Day2 T1 am
2024-08-24 22:33:21
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 ;
}
最新文章
- UE4 代码编写细节:静态变量
- hdu1241 Oil Deposits
- Android 利用Service实现下载网络图片至sdk卡
- 再论App的安全性
- rails中ActionController::InvalidAuthenticityToken解决办法
- Nginx之负载均衡
- 这是我用Microsoft Word 2010 直接发布的测试用博客
- 如何写angularJS模块
- eclipse 导入tomcat7源码
- mysql -- 备忘
- 【转】C++静态库与动态库
- oracle case when及decode的用法
- LINQ之道
- mysql数据库的查询,添加,删除,还原,备份
- 浅谈文件断点续传和WebUploader的基本结合
- CSS3圆角详解(border-radius)
- Java连接MySQL数据库详细教程(附网盘下载地址)
- 使用babel将ES6编译成ES5
- python作业学员管理系统(第十二周)
- Gradle for Android 翻译 -1