QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310331 | #5542. Doubled GCD | sdrailib# | WA | 0ms | 3796kb | C++14 | 1.0kb | 2024-01-21 11:15:30 | 2024-01-21 11:15:30 |
Judging History
answer
#include <bits/stdc++.h>
#include <queue>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ld=long double;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i];
map<int,int> mp;
set<int> ext;
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<n;i++){
int x=a[i];
int cnt=0;
while(x%2==0){
cnt++;
x/=2;
}
pq.push(cnt);
for(int j=3;x!=1;j+=2){
cnt=0;
while(x%j==0){
cnt++;
x/=j;
}
cout<<j<<" : "<<cnt<<'\n';
if(cnt==0&&mp.count(j)){
mp[j]=0;
}
else if(!ext.count(j)){
mp[j]=cnt;
ext.insert(j);
}
else{
mp[j]=min(mp[j],cnt);
}
}
}
while(pq.size()!=1){
int x=pq.top();pq.pop();
int y=pq.top();pq.pop();
pq.push(min(x,y)+1);
}
int ans=1;
for(int i=0;i<pq.top();i++)ans<<=1;
for(auto it:mp){
int tem=1;
for(int j=0;j<it.second;j++)tem*=it.first;
ans*=tem;
}
cout<<ans<<'\n';
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3796kb
input:
3 2 4 6
output:
3 : 1 24
result:
wrong answer 1st lines differ - expected: '8', found: '3 : 1'