QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310305 | #5542. Doubled GCD | sdrailib# | WA | 0ms | 3632kb | C++14 | 1.0kb | 2024-01-21 10:47:37 | 2024-01-21 10:47:38 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3632kb
input:
3 2 4 6
output:
3 : 1 24
result:
wrong answer 1st lines differ - expected: '8', found: '3 : 1'