QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94550 | #5866. Perfect Harmony | eyiigjkn | 0 | 731ms | 124700kb | C++14 | 1.5kb | 2023-04-06 17:17:57 | 2023-04-06 17:18:01 |
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,le);
}
if(ans<=R) printf("Case #%d: %lld\n",_,ans);
else printf("Case #%d: NO\n",_);
memset(ri+1,0,sizeof(ll)*n);
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 635ms
memory: 124700kb
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: 1666 Case #6: NO Case #7: NO Case #8: NO Case #9: NO Case #10: 5000 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 Case...
result:
wrong answer 5th lines differ - expected: 'Case #5: 9996', found: 'Case #5: 1666'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 731ms
memory: 124256kb
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: 5000000000000000 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:
wrong answer 3rd lines differ - expected: 'Case #3: 10000000000000000', found: 'Case #3: 5000000000000000'