NC16778. 黑妹的游戏III
描述
输入描述
第一行一个整数T表示数据的组数。(1 ≤ T ≤ 10)
对于每组数据：
第一行n表示序列的长度。(1 ≤ n ≤ 10000)
接下来一行n个整数ai表示序列的每个元素。(1 ≤ ai ≤ 108)
输出描述
对于每组数据输出一行表示答案。
示例1
输入:
3 3 1 2 3 4 8 8 9 9 5 4 8 12 18 22
输出:
6 1 66
C++14(g++5.4) 解法, 执行用时: 487ms, 内存消耗: 1876K, 提交时间: 2020-07-26 10:29:25
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int mod=1e9+7;
int n,res; unordered_map<int,int> mp,mx;
inline int qmi(int a,int b){
int res=1;
while(b){if(b&1) res=1LL*res*a%mod; a=1LL*a*a%mod; b>>=1;}
return res;
}
inline void solve(){
cin>>n;
mp.clear(),mx.clear(); res=1;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
for(int j=2;j*j<=x;j++) if(x%j==0){
int cnt=0;
while(x%j==0) x/=j,cnt++;
mp[j]+=cnt,mx[j]=max(mx[j],cnt);
}
if(x>1) mp[x]++,mx[x]=max(mx[x],1);
}
for(auto i:mp){
int x=i.first,y=i.second;
if(2*mx[x]<=y) res=1LL*res*(y%2?x:1)%mod;
else res=1LL*res*qmi(x,2*mx[x]-y)%mod;
}
printf("%d\n",res);
}
signed main(){
int T; cin>>T; while(T--) solve();
return 0;
}
C++ 解法, 执行用时: 463ms, 内存消耗: 1120K, 提交时间: 2021-11-24 15:44:36
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int mod=1e9+7;
int n,res; unordered_map<int,int> mp,mx;
inline int qmi(int a,int b){
int res=1;
while(b){if(b&1) res=1LL*res*a%mod; a=1LL*a*a%mod; b>>=1;}
return res;
}
inline void solve(){
cin>>n;
mp.clear(),mx.clear(); res=1;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
for(int j=2;j*j<=x;j++) if(x%j==0){
int cnt=0;
while(x%j==0) x/=j,cnt++;
mp[j]+=cnt,mx[j]=max(mx[j],cnt);
}
if(x>1) mp[x]++,mx[x]=max(mx[x],1);
}
for(auto i:mp){
int x=i.first,y=i.second;
if(2*mx[x]<=y) res=1LL*res*(y%2?x:1)%mod;
else res=1LL*res*qmi(x,2*mx[x]-y)%mod;
}
printf("%d\n",res);
}
signed main(){
int T; cin>>T; while(T--) solve();
return 0;
}