D. Almost All Divisors(数学分解因子)

时间:2022-05-13 08:39:00

其实这题并不难啊,但是分解因子的细节一定要小心。

\(比如样例48,2是因子说明24也是因子,也就是说假如x存在\)

\(那么x一定是因子中的最小数乘上最大数\)

\(那我们现在去验证x是否存在,先拿x去整除除数表,看看是否所有除数都是x的因子\)

\(然后再去判断x的因子个数是不是等于n(确保除数表包含所有因子)\)

\(考虑到d_i<=1e6,极端情况下x=1e12(我并不确定这种情况存在)\)

\(所以我们不一个一个判断sqrt(x)内的数是否是因子,而是采取短除法\)

ll x=zu,num=0,he=1;
for(int i=1;i<=cnt;i++)//用prime[]中的质数筛选
{
num=0;
if(x%prime[i]==0)
{
while(x%prime[i]==0) num++,x/=prime[i];
he*=(num+1);//包含num+1个prime[i]因子
}
}
if(x>1) he*=2;

\(比如说48=2^4*3^1,所以组合数学嘛,从2因子可以拿0,1,2,3,4个因子,有5种可能\)

\(从3因子可以拿0,1个因子两种可能,也就是总共5*2=10个因子\)

\(因为我们不能一个都不拿或者全部都拿(除数表不包括1和x),所以是10-2=8个因子\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+9;
ll t,n,a[301];
int prime[100009],cnt;
bool vis[maxn+10];
void make_prime()
{
for(int i=2;i<=maxn;i++)
{
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main()
{
cin>>t;
make_prime();
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
if(n>=2)
{
ll zu=a[1]*a[n],flag=1;
for(int i=2;i<=(n+1)/2;i++)//考虑奇数中间的数,所以(n+1)/2
{
if(a[i]*a[n-i+1]==zu) continue;
flag=0;
break;
}
if(flag==0) cout<<-1;
else
{
//判断zu有多少个因子
ll x=zu,num=0,he=1;
for(int i=1;i<=cnt;i++)//用prime[]中的质数筛选
{
num=0;
if(x%prime[i]==0)
{
while(x%prime[i]==0) num++,x/=prime[i];
he*=(num+1);//包含num+1个prime[i]因子
}
}
if(x>1) he*=2;
ll ans=0;
if(he-2==n) cout<<zu;
else cout<<-1;
}
}
else
{
if(vis[a[1]]) cout<<-1;
else cout<<a[1]*a[1];
}
cout<<endl;
}
}

D. Almost All Divisors(数学分解因子)的更多相关文章

  1. divisors 数学

    divisors 数学 给定\(m\)个不同的正整数\(a_1, a_2,\cdots, a_m\),请对\(0\)到\(m\)每一个\(k\)计算,在区间\([1, n]\)里有多少正整数是\(a\ ...

  2. uva 993 Product of digits &lpar;贪心 &plus; 分解因子&rpar;

      Product of digits  For a given non-negative integer number N , find the minimal natural Q such tha ...

  3. BZOJ&lowbar;4459&lowbar;&lbrack;Jsoi2013&rsqb;丢番图&lowbar;数学&plus;分解质因数

    BZOJ_4459_[Jsoi2013]丢番图_数学+分解质因数 Description 丢番图是亚历山大时期埃及著名的数学家.他是最早研究整数系数不定方程的数学家之一. 为了纪念他,这些方程一般被称 ...

  4. Codeforces Round &num;304 &lpar;Div&period; 2&rpar; D 思维&sol;数学&sol;质因子&sol;打表&sol;前缀和&sol;记忆化

    D. Soldier and Number Game time limit per test 3 seconds memory limit per test 256 megabytes input s ...

  5. HDU5812 Distance(枚举 &plus; 分解因子)

    题目 Source http://acm.hdu.edu.cn/showproblem.php?pid=5812 Description In number theory, a prime is a ...

  6. hdu 6069 Counting Divisors(求因子的个数)

    Counting Divisors Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Oth ...

  7. Divisors &lpar;求解组合数因子个数&rpar;【唯一分解定理】

    Divisors 题目链接(点击) Your task in this problem is to determine the number of divisors of Cnk. Just for ...

  8. Almost All Divisors(求因子个数及思维)

    ---恢复内容开始--- We guessed some integer number xx. You are given a list of almost all its divisors. Alm ...

  9. Educational Codeforces Round 89 &lpar;Rated for Div&period; 2&rpar; D&period; Two Divisors &lpar;数学&rpar;

    题意:有\(n\)组数,对于每组数,问是否能找到两个因子\(d_{1},d{2}\),使得\(gcd(d_{1}+d_{2},a_{i}=1)\),如果有,输出它们,否则输出\(-1\). 题解:对于 ...

随机推荐

  1. 移动web前端小结(一)--摘自小鹿&lowbar;同学

    一.框架 框架:Bootstrap+HTML5 Boilerplate. 两个框架整合到一起可以看一下这位大神的文章:<使用 Bootstrap 和 HTML5 Boilerplate 开始一个 ...

  2. vs操作快捷键

      注释:        先CTRL+K,然后CTRL+C取消注释: 先CTRL+K,然后CTRL+U 解析命名空间:shift+alt+f10   或Ctrl + .    调试快捷键 F6:   ...

  3. Android 适配多种ROM的快捷方式

    快捷方式 应该来说 很多人都做过,我们就来看一下基本的快捷方式 是怎么实现的,会有什么问题? 首先 肯定要获取权限: <!-- 添加快捷方式 --> <uses-permission ...

  4. 修改mysql编码为UTF-8

    mysql> show variables like '%character%'; +--------------------------+--------------------------- ...

  5. 为Android系统内置C可执行程序测试Linux内核驱动程序

    在前一篇文章中,我们介绍了如何在Ubuntu上为Android系统编写Linux内核驱动程序.在这个名为hello的Linux内核驱动程序中, 创建三个不同的文件节点来供用户空间访问,分别是传统的设备 ...

  6. &lbrack;leetcode-504-Base 7&rsqb;

    Given an integer, return its base 7 string representation. Example 1: Input: 100 Output: "202&q ...

  7. bzoj4361isn 容斥&plus;bit优化dp

    4361: isn Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 375  Solved: 186[Submit][Status][Discuss] ...

  8. linux定时备份学习笔记

    1.iterm2链接远程中文乱码 shh端vi ~/.bash_profile export LC_CTYPE=en_US.UTF-8 source ~/.bash_profile   2.WARNI ...

  9. php 1转成一

    function numToWord($num) { $chiNum = array('零', '一', '二', '三', '四', '五', '六', '七', '八', '九'); $chiUn ...

  10. 生产环境nginx配置文件&lpar;带https安全认证&rpar;

    #user www www; worker_processes 2; error_log logs/error.log info; pid /usr/local/nginx/nginx.pid; wo ...