做家具的网站有哪些,wordpress 批量添加用户权限,辽宁响应式网站费用,奇零seo赚钱培训题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/327/I 来源#xff1a;牛客网
现在处女座顺利的完成了测验#xff0c;处女座想要知道知道自己输出的结果是否正确。他希望知道自己有自己输出的数中有多少对是不满足要求的。 更具体的#xff0c…题干
链接https://ac.nowcoder.com/acm/contest/327/I 来源牛客网
现在处女座顺利的完成了测验处女座想要知道知道自己输出的结果是否正确。他希望知道自己有自己输出的数中有多少对是不满足要求的。 更具体的处女座想知道下面程序段的答案
int main()
{ int n; cinn; for (int i1;in;i) cina[i]; int ans0; for (int i1;in;i) { for (int ji1;jn;j) { if(τ(a[i]∗a[j])≤10)ansans1;if(τ(a[i]∗a[j])≤10)ansans1; } } coutansendl; return 0;
}
其中为n的因子的个数
输入描述: 两行
第一行一个整数n
第二行n个整数a1,a2,…,an
2n2000, 1ai3*108
输出描述:
一行一个整数ans
示例1
输入
复制
7
34 45 23 12 63 23 90输出
复制
3备注:
不保证任意两个整数互质
解题报告 直接暴力求解因为该范围内的数分解成素数最多就9个再加上大于4个就剪枝所以n^2log10完全不会超时。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includeunordered_map
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e4 5;
int n,a[MAX];
//vectorint vv[MAX];
mapint,int mp[MAX];
void ff(int id,int x) {for(int i 2; i*ix; i) {int cnt 0;if(x%i 0) {while(x%i0) x/i,cnt; mp[id][i] cnt;}}if(x 1) mp[id][x] 1;
}
int main()
{cinn;for(int i 1; in; i) scanf(%d,ai),ff(i,a[i]);int ans 0;for(int i 1; in; i) {if(mp[i].size() 4) continue;for(int j i1; jn; j) {if(mp[j].size() 4) continue;int nums 1;for(auto it : mp[i]) {int fac it.first;int num it.second;if(mp[j].find(fac) ! mp[j].end()) {nums * (num mp[j][fac]1);}else nums * (num1); }for(auto it : mp[j]) {int fac it.first;int num it.second;if(mp[i].find(fac) mp[i].end()) nums * (num1);}if(nums 10) ans;}} printf(%d\n,ans);return 0 ;
}