hihoCoder #1165 : 益智游戏 (挑战赛11 B题)
2024-09-29 01:47:46
题意:在一个序列中找到两个数a和b,使得a*b的因子个数最多,输出最多的因子个数。
思路:数据较多,处理会很慢。对序列中每个数字进行质数分解求因子个数,然后按照因子个数降序排列,对前50个因子最多的数进行暴力求两两之积的因子个数就行了。1s左右就能出结果。低于50的就会WA了。
#include <bits/stdc++.h>
using namespace std;
int a[];
pair<int,int> pa[];
int getAllFactors(int x, vector<int> &vect) //辅助!
{
for (int j = ; j * j <= x ; ++ j)
{
while (x % j == )
vect.push_back(j) , x /= j;
}
if(x>)
vect.push_back(x);
return vect.size();
} int getFactors(vector<int> &num)
{
vector< vector<int> > all;
all.resize(num.size());
for(int i=; i<num.size(); i++)
getAllFactors( num[i], all[i]); vector<int> tmp;
for(int i=; i<all.size(); i++)
tmp.insert(tmp.end(), all[i].begin(), all[i].end());
sort(tmp.begin(), tmp.end()); int z=;
for (int i = ; i < tmp.size() ; i++)
{
int l = i;
while (l < tmp.size() && tmp[l] ==tmp[i])
++ l;
z *= l - i + ;
i = l - ;
}
return z;
} int factors(int N)
{
if( == N) return ;
int cnt = ;
for (int j = ; j * j <= N ; j++)
{
if (N % j == )
{
cnt++;
if (j * j != N)
cnt++;
}
}
return cnt;
} int main() {
//freopen("input.txt", "r", stdin);
int t;
while(cin>>t)
{
for(int i=; i<t; i++)
{
scanf("%d",&a[i]);
pa[i]=make_pair(factors(a[i]),a[i]);
} sort(pa,pa+t);
reverse(pa,pa+t);
vector<int> tmp;
int n = t>? : t;
int ans=;
for(int i=; i<n; i++)
{
for(int j=i; j<n; j++)
{
tmp.clear();
tmp.push_back(pa[i].second);
tmp.push_back(pa[j].second);
ans=max(getFactors(tmp), ans);
}
}
cout<<ans<<endl;
}
return ;
}
AC代码
最新文章
- Android -- 服务组件的使用(1)
- sp_executesql
- Base64编码解码
- [转自51CTO]ITIL与ISO20000的关系
- 后序/中序--->;前序
- 1.C#基础篇-->;封装、继承和多态
- linux中的配置文件
- 自我理解foreach工作原理
- SQLSERVER内核架构剖析 (转)
- Android的selector 背景选择器
- Handler和Message以及Looper之间的三角关系
- 睡不着,复习一下C++基础中的基础(深拷贝与浅拷贝)
- Boost库安装(实测vs2012)
- Bootstrap table 元素列内容超长自动折行显示方法?
- js模块化规范
- 写论文时,使用word的一些技巧
- Android 中的设计模式
- mybatis教程之原理剖析
- cetnos 7 增加新的硬盘
- GridControl 分组排序