QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94551 | #5866. Perfect Harmony | eyiigjkn | 43 ✓ | 734ms | 125388kb | C++14 | 1.6kb | 2023-04-06 17:21:03 | 2023-04-06 17:21:05 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=1e8;
constexpr ll INF=1e18;
int prime[10000010],m=0,tot;
ll a[10010],ri[10010],P[20],C[20];
bool npri[100000010];
inline void chkmin(ll &x,const ll &y){x=min(x,y);}
ll dfs(int d,ll cur,ll le)
{
if(d>tot) return cur>=le?cur:INF;
ll ans=dfs(d+1,cur,le);
for(int i=1;i<=C[d];i++) chkmin(ans,dfs(d+1,cur*=P[d],le));
return ans;
}
ll calc(ll n,ll le)
{
tot=0;
for(int i=1;i<=m && prime[i]*prime[i]<=n;i++)
if(n%prime[i]==0)
{
P[++tot]=prime[i];C[tot]=0;
for(;n%P[tot]==0;n/=P[tot]) C[tot]++;
}
if(n>1) P[++tot]=n,C[tot]=1;
return dfs(1,1,le);
}
int main()
{
int T,n;
ll L,R;
npri[1]=1;
for(int i=2;i<=N;i++)
{
if(!npri[i]) prime[++m]=i;
for(int j=1;j<=m && i*prime[j]<=N;j++)
{
npri[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
cin>>T;
for(int _=1;_<=T;_++)
{
ll ans=INF;
scanf("%d%lld%lld",&n,&L,&R);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
for(int i=n;i;i--) ri[i]=__gcd(ri[i+1],a[i]);
ll le=1;
if(ri[1]>=L) chkmin(ans,calc(ri[1],L));
for(int i=1;i<=n;i++)
{
ll t=__gcd(le,a[i]);
if(le/t>R/a[i]) break;
le=le/t*a[i];
if(i<n)
{
if(le>ri[i+1] || ri[i+1]%le || ri[i+1]<L) continue;
else if(le<L) chkmin(ans,le*calc(ri[i+1]/le,(L+le-1)/le));
else chkmin(ans,le);
}
else chkmin(ans,(L+le-1)/le*le);
}
if(ans<=R) printf("Case #%d: %lld\n",_,ans);
else printf("Case #%d: NO\n",_);
memset(ri+1,0,sizeof(ll)*n);
}
return 0;
}
詳細信息
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 639ms
memory: 125388kb
input:
40 3 2 100 3 5 7 4 8 16 1 20 5 2 7 5 10000 9942 9762 9822 9978 9714 9678 9726 4 2 10000 3 17 4 49 10 8331 9997 238 833 34 2 119 98 49 7 17 14 5 3299 8227 4863 6630 5752 498 4148 5 5899 7578 4808 3143 8259 9828 6133 5 3477 3514 2755 1104 6009 8970 3195 5 5795 6372 2431 3458 3070 4892 9336 2 5001 1000...
output:
Case #1: NO Case #2: 10 Case #3: 6 Case #4: 9996 Case #5: 9996 Case #6: NO Case #7: NO Case #8: NO Case #9: NO Case #10: 10000 Case #11: NO Case #12: NO Case #13: NO Case #14: 15 Case #15: NO Case #16: 1 Case #17: 2310 Case #18: 23 Case #19: NO Case #20: NO Case #21: NO Case #22: NO Case #23: NO Cas...
result:
ok 40 lines
Subtask #2:
score: 35
Accepted
Test #2:
score: 35
Accepted
time: 734ms
memory: 124180kb
input:
40 3 2 100 3 5 7 4 8 16 1 20 5 2 2 5000000000000001 10000000000000000 2500000000000000 5000000000000000 2888 2 10000000000000000 15661 20393 4889 14929 26053 10529 2897 13009 15361 2707 12619 22153 1453 21739 3709 1151 25033 22157 18919 25733 25579 15643 14029 15101 8447 1381 7669 797 9419 1129 1795...
output:
Case #1: NO Case #2: 10 Case #3: 10000000000000000 Case #4: NO Case #5: 9999999999999996 Case #6: 304250263527210 Case #7: NO Case #8: 223092870 Case #9: 6469693230 Case #10: NO Case #11: 302977 Case #12: NO Case #13: 1 Case #14: NO Case #15: 6064949221531200 Case #16: 4900956 Case #17: NO Case #18:...
result:
ok 40 lines
Extra Test:
score: 0
Extra Test Passed