处女座的测验（二）

本文主要是介绍处女座的测验（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

现在处女座顺利的完成了测验，处女座想要知道知道自己输出的结果是否正确。他希望知道自己有自己输出的数中有多少对是不满足要求的。

更具体的，处女座想知道下面程序段的答案

int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int ans=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(τ(a[i]∗a[j])≤10)ans=ans+1;cout<<ans<<endl;return 0;
}

其中为 n 的因子的个数

【输入描述】

两行

第一行一个整数n

第二行n个整数，a1,a2,…,an

2<=n<=2000, 1<=ai<=3*10^8

【输出描述】

一行，一个整数ans

【样例】

示例1

输入
7
34 45 23 12 63 23 90
输出
3

【备注】

不保证任意两个整数互质

思路：

先打素数表，然后用 vector 存储每个数的素因子以及素因子的幂数，最后用 map 存储 x*y 的素因子的最高次数用题目给的公式求出 ? 即可

要注意的是，如果两个数中有个数的 ? 大于 10，那么需要剪枝

【源代码】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define N 100001
#define LL long long
using namespace std;
int a[N];
int prime[N],cnt;
bool bprime[N];
vector<int> power[N];//幂数
vector<int> num[N];//素因子
void make_prime()
{memset(bprime,true,sizeof(bprime));bprime[0]=false;bprime[1]=false;for(int i=2;i<=N;i++){if(bprime[i]){prime[cnt++]=i;for(int j=i*2;j<=N;j+=i)bprime[j]=false;}}
}
int main(){make_prime();int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==1){//数为1的情况power[i].push_back(1);num[i].push_back(1);}else{for(int j=0;prime[j]*prime[j]<=a[i];j++){//枚举a[i]的素因子if(a[i]%prime[j]==0){num[i].push_back(prime[j]);//记录素因子int cnt=0;while(a[i]%prime[j]==0){cnt++;a[i]/=prime[j];}power[i].push_back(cnt);//记录幂数}}//考虑a[i]自身if(a[i]!=1){num[i].push_back(a[i]);power[i].push_back(1);}}}int res=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){map<int,int> mp;//存储x*y素因子的最高次数for(int k=0;k<num[i].size();k++)mp[num[i][k]]+=power[i][k];for(int k=0;k<num[j].size();k++)mp[num[j][k]]+=power[j][k];int t=1;map<int,int>::iterator it;for(it=mp.begin();it!=mp.end();it++)t=t*(it->second+1);if(t<=10)//剪枝，不考虑t大于10的数res++;}}printf("%d\n",res);return 0;
}

 

这篇关于处女座的测验（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---