Heritage of skywalkert
2024-09-25 22:03:01
Heritage of skywalkert
skywalkert, the new legend of Beihang University ACM-ICPC Team, retired this year leaving a group of newbies again.
Rumor has it that he left a heritage when he left, and only the one who has at least 0.1% IQ(Intelligence Quotient) of his can obtain it.
To prove you have at least 0.1% IQ of skywalkert, you have to solve the following problem:
Given n positive integers, for all (i, j) where 1 ≤ i, j ≤ n and i ≠ j, output the maximum value among . means the Lowest Common Multiple.
输入描述:
The input starts with one line containing exactly one integer t which is the number of test cases. (1 ≤ t ≤ 50) For each test case, the first line contains four integers n, A, B, C. (2 ≤ n ≤ 107, A, B, C are randomly selected in unsigned 32 bits integer range)
The n integers are obtained by calling the following function n times, the i-th result of which is ai, and we ensure all ai > 0. Please notice that for each test case x, y and z should be reset before being called.
No more than 5 cases have n greater than 2 x 106.
输出描述:
For each test case, output "Case #x: y" in one line (without quotes), where x is the test case number (starting from 1) and y is the maximum lcm.
输入例子:
2
2 1 2 3
5 3 4 8
输出例子:
Case #1: 68516050958
Case #2: 5751374352923604426
-->
输入
2
2 1 2 3
5 3 4 8
输出
Case #1: 68516050958
Case #2: 5751374352923604426
题意:n个数求任意两个数的最大的最小公倍数。
暴力模拟了一些数据发现答案的那两个数总是前15大的数,意思就是只有前15大的数才可能组合出答案。
于是用优先队列维护前15大的数,要注意最好尽量减少pop的操作,以免超时。
#include<bits/stdc++.h>
using namespace std;
unsigned int x,y,z;
unsigned int f()
{
unsigned int t;
x^=x<<;
x^=x>>;
x^=x<<;
t=x;
x=y;
y=z;
z=t^x^y;
return z;
} priority_queue<unsigned long long,vector<unsigned long long>,greater<unsigned long long> >team; unsigned long long gcd(unsigned long long a,unsigned long long b)
{
if(a%b==)return b;
return gcd(b,a%b);
} int tot=;
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d %u %u %u",&n,&x,&y,&z); for(int i=; i<=n; i++)
{
unsigned long long now=f(); if(team.size()>=&&team.top()>=now)continue;
team.push(now);
if(team.size()>)team.pop();
} unsigned long long now[];
unsigned long long ans=;
int c1=;
while(!team.empty())
{
now[c1++]=team.top();
team.pop();
} for(int i=; i<c1; i++)
for(int j=; j<c1; j++)
if(i!=j)ans=max(ans,now[i]/gcd(now[i],now[j])*now[j]); printf("Case #%d: %llu\n",tot++,ans);
}
return ;
}
最新文章
- spring aop注解配置
- ORACLE10g创建表空间,角色与授权
- MVC增删改查例子
- js-------》(小效果)实现倒计时及时间对象
- MITK Tutorial
- ural 1123
- mysql修改root密码的方法
- CSS样式设置语法全解,样式优先级、值和单位、字体、文本、块级元素,行内元素,替换元素、非替换元素、display、float、position、table、li、光标、边距边框、轮廓、颜色背景
- WPF学习之路一
- vue基础学习(一)
- Boosting(提升方法)之AdaBoost
- linux的自有(内置)服务
- 自动化测试-9.selenium多窗口句柄的切换
- Redis淘汰删除策略
- shell if 语句
- excel技巧--多行排成单列
- 【WP8】自定义控件
- RPM 安装oracle18c 修改字符集的方法
- 《C#高级编程》学习笔记----c#内存管理--栈VS堆
- 记录一下我的mac的环境变量的配置参数