Masquerade strikes back Gym - 101911D (数学)
Quite often the jury of Saratov SU use the problem "Masquerade" in different practice sessions before the contest. This problem is quite easy — all you need is to print the product of two integers which were read from the input stream.
As usual, the jury had prepared this problem once again. The jury had nn testcases, the ii -th testcase was a pair of positive integers aiai and bibi , both integers didn't exceed 107107 . All testcases were pairwise distinct.
Unfortunately, something went wrong. Due to hardware issues all testcases have disappeared. All that the jury were able to restore are the number of testcases nn and the answers to these testcases, i. e. a sequence of nn numbers c1,c2,…,cnc1,c2,…,cn , such that ai⋅bi=ciai⋅bi=ci .
The jury ask you to help them. Can you provide any possible testset? Remember that all testcases were distinct and all numbers in each testcase were positive integers and didn't exceed 107107 .
Input
First line contains one insteger nn (1≤n≤2⋅1051≤n≤2⋅105 ) — the number of lost testcases.
Second line contains nn space-separated integers c1,c2,…,cnc1,c2,…,cn (1≤ci≤1071≤ci≤107 ) — the answers to the testcases.
Output
If there is no such testset, print NO.
Otherwise, print YES in first line. Then print nn more lines, the ii -th of them should contain two space separated positive integers aiai and bibi not exceeding 107107 . All pairs (ai,bi)(ai,bi) must be distinct, and, for each i∈[1,n]i∈[1,n] , the condition ai⋅bi=ciai⋅bi=ci must be met.
Examples
4
1 3 3 7
YES
1 1
1 3
3 1
1 7
5
3 1 3 3 7
NO
6
9 10 9 10 9 10
YES
1 9
1 10
3 3
5 2
9 1
2 5
Note
In the first example one of the possible testsets is (a1=1a1=1 , b1=1b1=1 ), (a2=1a2=1 , b2=3b2=3 ), (a3=3a3=3 , b3=1b3=1 ), (a4=1a4=1 , b4=7b4=7 ).
In the second example a testset consisting of distinct tests doesn't exist.
题意:给出n个数,让你将每个数都表示成两个数相乘,但是不能重复,(1*3和3*1不算重复)可以就输出结果,否则输出NO
思路:对于给出的数里,相同的数我们可以一起处理,即可以先排序,然相同的数挨在一起,我们可以统计其个数,然后在这个数开方范围内寻找因子。最后统计该数出现的个数和式子数时候满足要求,即式子是否足够多。
#include<bits/stdc++.h>
using namespace std; int n; struct E
{
int val;
int index;
} e[]; bool cmp(E a,E b)
{
return a.val < b.val;
} int ll[];
int rr[];
int main()
{
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d",&e[i].val);
e[i].index = i;
}
sort(e+,e++n,cmp);
int cnt = ;
int flag = ;
for(int i=; i<=n; i++)
{
int l=i,r=i;
while(r+<=n && e[r].val == e[r+].val)
r++;
for(int j=; j*j<=e[i].val; j++)
{
if(e[i].val % j == )
{
ll[e[l].index] = j;
rr[e[l].index] = e[i].val / j;
l++;
if(l > r)break;
if(j * j != e[i].val)
{
ll[e[l].index] = e[i].val / j;
rr[e[l].index] = j;
l++;
if(l > r)break;
}
}
}
if(l <= r)
{
flag = ;
break;
}
i = r;
}
if(flag)printf("NO\n");
else
{
printf("YES\n");
for(int i=;i<=n;i++)
{
printf("%d %d\n",ll[i],rr[i]);
}
}
}
最新文章
- iOS 限制TextField输入长度(标准)
- NSUserDefaults的使用
- Oracle SQL Developer 添加SQLServer 和Sybase 连接
- 【转】python编码规范
- Sql合并两个select查询
- ubuntu默认root密码
- 转载:Windows Phone 8.1 投影我的屏幕使用教程
- stringstream vs sprintf, sscanf.
- LRU算法&;amp;&;amp;LeetCode解题报告
- Entity Framework 学习初级篇3-- LINQ TO Entities
- EntityFramewok Core 1.1连接MSSql数据库详解
- axios - 基于 Promise 的 HTTP 异步请求库
- 仿迅雷播放器教程 -- 基于VLC的MFC播放器 (6)
- Linux 下安装JDK和jmeter 及环境配置记录过程
- (转)Elasticsearch查询规则------match和term
- Oracle时间的加减
- 002-mybatis主配置文件
- devise修改密码
- 【转】2012年7月12 – 腾讯公司 WEB高级应用开发工程师 最新面试题
- 33、深入理解Java的接口和抽象类