hiho 1165 益智游戏（因子个数+贪心）

本文主要是介绍hiho 1165 益智游戏（因子个数+贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个数组中有n个数  现在要从这个数组里面随机挑选两个数（可能相同） 

使得这两个数相乘所得数中因子个数最多

一开始想的就是把数组中所有数进行素因子分解 保存素因子的个数 

然后枚举 从数组中挑选两个数的情况 相乘 根据素因子的情况求出因子个数

显然会tle

在这里可以贪心 根据数分解后得到的素因子种类的个数和素因子总的个数 进行排序

选取前面的100个进行枚举计算就可以了。。。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 100010
#define MAXM 100010
#define INF 99999999
#define ll long long
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int a[100010];int num[100];struct node
{int id,cnt1,cnt2;//cnt1代表质因子的种类数 cnt2代表质因子总的个数bool operator<(const node &no)const{if(cnt1!=no.cnt1) return cnt1>no.cnt1;else return cnt2>no.cnt2;}
}no[MAXN];void divide(int id)
{int x=a[id];no[id].cnt1=no[id].cnt2=0; no[id].id=id;for(int i=2;i*i<=x;i++){if(x%i==0){no[id].cnt1++;while(x%i==0){no[id].cnt2++; x/=i;}}}if(x>1){no[id].cnt1++; no[id].cnt2++;}
}ll cal(ll x)
{MEM(num,0);int cnt=0;for(ll i=2;i*i<=x;i++){if(x%i==0){cnt++;while(x%i==0){num[cnt]++; x/=i;}}}if(x>1) num[++cnt]++;ll res=1;for(int i=1;i<=cnt;i++){
//        cout<<"i "<<num[i]<<endl;res*=(num[i]+1);}return res;
}int main()
{//fread;
//    prime();
//    cout<<"k "<<k;
//    for(int i=0;i<k;i++)
//        cout<<p[i]<<" ";int n;while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++){scanf("%d",&a[i]);divide(i);}sort(no,no+n);n=min(n,100);ll ans=0;for(int i=0;i<n;i++)for(int j=0;j<n;j++){ll tmp=(ll)a[no[i].id]*a[no[j].id];ans=max(ans,cal(tmp));}cout<<ans<<endl;}return 0;
}

这篇关于hiho 1165 益智游戏（因子个数+贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---